865. 具有所有最深节点的最小子树-dfs遍历

865. 具有所有最深节点的最小子树

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

返回包含原始树中所有 最深节点 的 最小子树 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的 子树 是该节点加上它的所有后代的集合。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

这题还是挺有意思的，解题代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int get_deep(struct TreeNode* root){
    if(root){
        int a=get_deep(root->right)+1;
        int b=get_deep(root->left)+1;
        return fmax(a,b);
    }
    else{
        return 0;
    }
}

int get_num(struct TreeNode* root,int deep){
    if(root){
         if(deep==1){
            return 1;
        }
      
        int a=get_num(root->right,deep-1);
        int b=get_num(root->left,deep-1);
        return a+b;
         
    }
    else{
        return 0;
    }
}


int get_node(struct TreeNode* root,int deep,struct TreeNode **re,int sum){
    if(root&&(*re)==NULL){


          if(deep==1){
            if(sum==1){
                *re=root;
                return 2;
            }

            return 1;
        }
      
        int a=get_node(root->right,deep-1,re,sum);
        int b=get_node(root->left,deep-1,re,sum);
        if(a+b==sum){
            *re=root;
            a=a+1;
            b=b+1;
        }

        return a+b;
        
    }
    else{
        return 0;
    }
}
struct TreeNode* subtreeWithAllDeepest(struct TreeNode* root){
    struct TreeNode *re;
    re=NULL;
    int deep=get_deep(root);
    int sum=get_num(root,deep);
   // printf("%d deep %d",sum,deep);
   int a= get_node(root,deep,&re,sum);
  
    return re;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77