具有所有最深结点的最小子树

╰半橙微兮° 2022-12-08 15:37 126阅读 0赞

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

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

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

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

示例：

输入：\[3,5,1,6,2,0,8,null,null,7,4\]  
输出：\[2,7,4\]  
解释：

我们返回值为 2 的结点，在图中用黄色标记。  
在图中用蓝色标记的是树的最深的结点。  
输入 “\[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4\]” 是对给定的树的序列化表述。  
输出 “\[2, 7, 4\]” 是对根结点的值为 2 的子树的序列化表述。  
输入和输出都具有 TreeNode 类型。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一道题搞了两个多小时，还是太不熟练了，有点类似之前碰到的好叶子节点对，不过由于要找最小子树，所以最核心的前序遍历变成了后序遍历，我的代码思路是先前序遍历找到最大深度值，之后用这个最大深度值再前序遍历找到所有最大深度的结点。之后再后序遍历，对于每一个结点，找他左右子树是否包含了所有最大深度结点，具体方法就是开个lefts数组和rights数组，然后分别前序遍历来找。需要注意的是只有一个最大深度结点的时候，需要单独判断。还有就是一找到满足条件的就弹出，所以我设置了一个judge变量，在各个递归结束的地方都判断该judge变量，来一直向上层弹出。  
具体代码如下：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
     # include<iostream>
     # include<vector>
     # include<queue>
     using namespace std;
    class Solution { 
    public:
        TreeNode* subtreeWithAllDeepest(TreeNode* root) { 
            vector<TreeNode *> maxVector;
            vector<int> resArray;
            TreeNode * res=root;
            int max=0;
            dfsMax(root,0,max);
            searchMax(root,maxVector,max,0);
            bool judge=false;
            bw(root,maxVector,max,judge,res,0);
            return res;
        }
        void bw(TreeNode *root,vector<TreeNode *> &maxVector,int max,bool &judge,TreeNode * &res,int depth){ 
            if(root==NULL||judge) return;
            bw(root->left,maxVector,max,judge,res,depth+1);
            if(judge) return;
            bw(root->right,maxVector,max,judge,res,depth+1);
            if(judge) return;
            if(maxVector.size()==1&&root->left==NULL&&root->right==NULL&&depth==max){ 
                res=root;
                judge=true;
                return;
            }
            vector<TreeNode *> lefts;
            findMax(root->left,max,lefts,depth+1);
            vector<TreeNode *> rights;
            findMax(root->right,max,rights,depth+1);
            int tot=lefts.size()+rights.size();
            if(tot==maxVector.size()){ 
                res=root;
                judge=true;
            }
    
        }
        void findMax(TreeNode *root,int max,vector<TreeNode *> &maxArray,int depth){ 
            if(root==NULL) return;
            if(depth==max) { maxArray.push_back(root); return;}
            findMax(root->left,max,maxArray,depth+1);
            findMax(root->right,max,maxArray,depth+1);
        }
        void dfsMax(TreeNode *root,int depth,int &max){ 
            if(root==NULL) return;
            if(depth>=max) { max=depth;}
            dfsMax(root->left,depth+1,max);
            dfsMax(root->right,depth+1,max);
        }
        void searchMax(TreeNode *root,vector<TreeNode *> &maxVector,int max,int depth){ 
            if(root==NULL) return;
            if(depth==max) { maxVector.push_back(root); return;}
            searchMax(root->left,maxVector,max,depth+1);
            searchMax(root->right,maxVector,max,depth+1);
        }
    };

之后看了看别人写的，发现更简单的做法：若一个结点左右子树深度相等，则该结点就是要求的最小子树，若左子树深度大于右子树，则最小子树在左子树上，递归左子树，反之递归右子树。代码如下：