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

leetcode - Maximum Depth of Binary Tree

2024-07-07 15:55:25   228人阅读

题目：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

 


联系
我们