求二叉樹的最大深度，簡(jiǎn)單DFS/BFS
DFS版
1 #104
2 #Runtime: 32 ms (Beats 40.47%)
3 #Memory: 16 MB (Beats 56.57%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 max_depth = 1
13 def DFS_Tree(self, root, depth):
14 self.max_depth = max(self.max_depth, depth)
15 if root.left != None:
16 self.DFS_Tree(root.left, depth + 1)
17 if root.right != None:
18 self.DFS_Tree(root.right, depth + 1)
19 return
20 def maxDepth(self, root):
21 """
22 :type root: TreeNode
23 :rtype: int
24 """
25 if root == None:
26 return 0
27 self.DFS_Tree(root, 1)
28 return self.max_depth
BFS版
C++
1 //104
2 //Runtime: 44 ms (Beats 5.10%)
3
4 /**
5 * Definition for binary tree
6 * struct TreeNode {
7 * int val;
8 * TreeNode *left;
9 * TreeNode *right;
10 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 * };
12 */
13 class Solution {
14 public:
15 struct Que {
16 TreeNode *pt;
17 int depth;
18 }que[10010];
19 int maxDepth(TreeNode *root) {
20 if(root == NULL) return 0;
21 int l = 0, r = 1;
22 que[0].pt = root;
23 que[0].depth = 1;
24 while(l < r) {
25 TreeNode *tp = que[l].pt;
26 if(tp->left != NULL) {
27 que[r].pt = tp->left;
28 que[r].depth = que[l].depth + 1;
29 ++r;
30 }
31 if(tp->right != NULL) {
32 que[r].pt = tp->right;
33 que[r].depth = que[l].depth + 1;
34 ++r;
35 }
36 ++l;
37 }
38 return que[r - 1].depth;
39 }
40 };
Python
1 #104
2 #Runtime: 27 ms (Beats 71.22%)
3 #Memory: 16.2 MB (Beats 37.34%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def maxDepth(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 ans = 0
18 if root:
19 q = deque([(root, 1)])
20 while q:
21 node, dep = q.popleft()
22 ans = max(ans, dep)
23 if node.left:
24 q.append((node.left, dep + 1))
25 if node.right:
26 q.append((node.right, dep + 1))
27 return ans