首页 > 代码库 > leetcode - Maximum Depth of Binary Tree

leetcode - Maximum Depth of Binary Tree

题目:Maximum Depth of Binary Tree

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.

 

个人思路:

1、采取递归的方式先序遍历(或者深度优先搜索)树中的每个节点

2、每当进入新的一层递归时,临时深度(记录当前遍历的节点深度的变量)加1,从左节点或者右节点返回时临时深度减1,若此时遍历到叶子节点(即左右节点均为NULL),则判断最终深度(记录已遍历过节点的最大深度)与临时深度哪个大,若临时深度大,则将临时深度赋给最终深度,若最终深度大,则不做处理

 

代码(测试代码可以删去,提交必要代码即可):

 1 #include <stddef.h>
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 struct TreeNode
 7 {
 8     int val;
 9     TreeNode *left;
10     TreeNode *right;
11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 };
13 
14 class Solution
15 {
16 public:
17     Solution() : depth(0), tmp_depth(0) {};
18     int maxDepth(TreeNode *root)
19     {
20         if (root == NULL) //根节点为空,返回0
21         {
22             return depth;
23         }
24         ++tmp_depth;
25         if (root->left != NULL)
26         {
27             maxDepth(root->left);
28             --tmp_depth;
29         }    
30         if (root->right != NULL)
31         {
32             maxDepth(root->right);
33             --tmp_depth;
34         }    
35         if (root->left == NULL && root->right == NULL)
36         {
37             if (depth < tmp_depth)
38             {
39                 depth = tmp_depth;
40             }
41         }
42         
43         return depth;
44     };
45 private:
46     int depth;
47     int tmp_depth;
48 };
49 
50 int main()
51 {
52     TreeNode *root = new TreeNode(1);
53     root->left = new TreeNode(2);
54     root->right = new TreeNode(2);
55     TreeNode *root_left = root->left;
56     root_left->left = new TreeNode(3);
57     root_left->right = new TreeNode(3);
58     TreeNode *root_left_right = root_left->right;
59     root_left_right->right = new TreeNode(4);
60 
61     Solution s;
62     int depth = s.maxDepth(root);
63     cout << depth << endl;
64 
65     system("pause");
66     return 0;
67 }
View Code

 

网上找到更加精简的代码,看来我的基础还有待提高,在这分享,链接:http://www.cnblogs.com/remlostime/archive/2012/11/12/2766574.html

 

思路:

1、一个树的深度是其左子树与右子树较大者加1

2、深度优先搜索遍历即可

代码:

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int maxDepth(TreeNode *root) {
13         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         if (root == NULL)
16             return 0;
17             
18         int leftDepth = maxDepth(root->left);
19         int rightDepth = maxDepth(root->right);
20         
21         return max(leftDepth, rightDepth) + 1;
22     }
23 };
View Code