Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
For example:
Given binary tree [3,9,20,null,null,15,7]
,
3 / 9 20 / 15 7
return its depth = 3.
解法1:
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 return max(self.maxDepth(root.left)+1, self.maxDepth(root.right)+1)
解法2: BFS
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 q = [root] ans = 0 while q: ans += 1 q = [y for x in q for y in (x.left, x.right) if y] return ans
DFS的迭代解法:在迭代tree node的过程中,使用另外一个stack追踪每一个node的高度。
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 nodes = [root] heights = [1] ans = 0 while nodes: n = nodes.pop() h = heights.pop() ans = max(ans, h) if n.right: nodes.append(n.right) heights.append(h+1) if n.left: nodes.append(n.left) heights.append(h+1) return ans