LeetCode 865. Smallest Subtree with all the Deepest Nodes

LeetCode 865. Smallest Subtree with all the Deepest Nodes
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说LeetCode 865. Smallest Subtree with all the Deepest Nodes,希望能够帮助大家进步!!!

树的题递归来做。给定一个root,如果左右两颗子树height一样,那么root就是所求的解;如果不一样,那么解一定再height高的那棵子树里,递归调用即可。height和depth的区别:What is the difference between tree depth and height?

本题tricky的地方在于,我们既要在dfs时返回树的height做判断,又要返回TreeNode *作为解。

我们可以建立一个pair来同时返回,也可以通过引用传递来返回。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
    
    pair<int,TreeNode *> dfs(TreeNode *root){
        // return the height of subtree rooted at root, and the ans
        if (root==NULL){
            return {-1,NULL};
        }
        auto l=dfs(root->left);
        auto r=dfs(root->right);
        if (l.first==r.first) return {l.first+1,root};
        return {max(l.first, r.first)+1, l.first>r.first ? l.second : r.second};
    }
};

时间复杂度 O(n)

转载于:https://www.cnblogs.com/hankunyan/p/11200802.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29655

发表评论