题目地址：Minimum Depth of Binary Tree - LeetCode
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
这道题目是计算二叉树最小高度，可以用迭代或者递归来做。
递归解法如下。 Python解法如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
def helper(root, height):
if root == None:
return height-1
if root.left == None and root.right == None:
return height
elif root.left == None:
return helper(root.right, height+1)
elif root.right == None:
return helper(root.left, height+1)
return min(helper(root.left, height+1), helper(root.right, height+1))
return helper(root, 1)
迭代的解法如下。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
if root is None:
return 0
stack=[(1,root)]
height=1
while stack!=[]:
depth,root=stack.pop(0)
child=[root.left,root.right]
if not any(child):
height=max(depth,height)
return height
for i in child:
if i is not None:
stack.append((depth+1,i))
return height
文档信息
- 本文作者：last2win
- 本文链接：https://last2win.com/2020/01/15/LeetCode-111/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）