Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求二叉树的最大深度,简单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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理