C++剑指offer(面试题55 - I. 二叉树的深度)【递归】

糖逗

题目描述：

1. 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
   
2. 
   
3. 例如：
   
4. 
   
5. 给定二叉树 [3,9,20,null,null,15,7]，
   
6. 
   
7.     3
   
8.    / \
   
9.   9  20
   
10.     /  \
    
11.    15   7
    
12. 返回它的最大深度 3 。
    
13. 
    
14.  
    
15. 
    
16. 提示：
    
17. 
    
18. 节点总数 <= 10000
    
19. 
    
20. 来源：力扣（LeetCode）
    
21. 链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof
    
22. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <vector>
   
2. #include <iostream>
   
3. #include <malloc.h>
   
4. 
   
5. 
   
6. using namespace std;
   
7. 
   
8. struct TreeNode{
   
9.         int val;
   
10.         TreeNode*left;
    
11.         TreeNode*right;
    
12.         TreeNode(int x):val(x), left(NULL), right(NULL){
    
13.         }
    
14. };
    
15. 
    
16. TreeNode* Create(vector<int> input){
    
17.         TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
    
18.         for(int i= 0; i < input.size(); i++){
    
19.                 res[i].val = input[i];
    
20.                 res[i].left = NULL;
    
21.                 res[i].right = NULL;
    
22.         }
    
23.         for(int i = 0; i < input.size()/2-1; i++){
    
24.                 if(2*i+1 <= input.size()){
    
25.                         res[i].left = &res[2*i+1];
    
26.                 }
    
27.                 if(2*i+2 < input.size()){
    
28.                         res[i].right =  &res[2*i+2];
    
29.                 }
    
30.         }
    
31.         return res;
    
32. }
    
33. 
    
34. int solution(TreeNode* root){
    
35. 
    
36.         if(root == NULL) return 0;
    
37.         return 1+max(solution(root->left), solution(root->right));
    
38. 
    
39. }
    
40. 
    
41. int main(void){
    
42.         vector<int> input;
    
43.         int number;
    
44.         while(cin >> number){
    
45.                 input.push_back(number);
    
46.         }
    
47.        
    
48.         TreeNode*root = Create(input);
    
49.        
    
50.         int res = solution(root);
    
51.         cout << res << endl;
    
52.         return 0;
    
53. }

复制代码

注意事项：
1.暂无。

糖逗