做韩国网站,iis怎么配置网站,企业网盘怎么下载文件,手机网站欣赏1. 题目
给定一个根为 root 的二叉树#xff0c;每个结点的深度是它到根的最短距离。
如果一个结点在整个树的任意结点之间具有最大的深度#xff0c;则该结点是最深的。
一个结点的子树是该结点加上它的所有后代的集合。
返回能满足“以该结点为根的子树中包含所有最深的…1. 题目
给定一个根为 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 类型。提示
树中结点的数量介于 1 和 500 之间。
每个结点的值都是独一无二的。 来源力扣LeetCode 链接https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似的题LeetCode 1123. 最深叶节点的最近公共祖先递归比较子树高度 跟链接的题是一个意思表述不太一样。
class Solution {
public:TreeNode* subtreeWithAllDeepest(TreeNode* root) {if(!root)return NULL;int hl height(root-left);int hr height(root-right);if(hl hr)return root;else if(hl hr)return subtreeWithAllDeepest(root-right);elsereturn subtreeWithAllDeepest(root-left);}int height(TreeNode* root){if(!root)return 0;return 1max(height(root-left),height(root-right));}
};
上面解法有很多冗余的重复遍历
优化
class Solution {
public:TreeNode* subtreeWithAllDeepest(TreeNode* root) {return dfs(root).second;}pairint, TreeNode* dfs(TreeNode* root)//返回深度节点{if(!root)return {0, NULL};pairint, TreeNode* l dfs(root-left);pairint, TreeNode* r dfs(root-right);if(l.first r.first)//左右高度一样返回当前root深度返回时都要1return {l.first1, root};else if(l.first r.first)return {l.first1, l.second};//左边高返回左边找到的节点elsereturn {r.first1, r.second};}
};
