速推网,湖南广告优化,2018网站建设合同范本,微信上打开连接的网站怎么做本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个有根节点 root 的二叉树返回它 最深的叶节点的最近公共祖先 。
回想一下
叶节点 是二叉树中没有子节点的节点树的根节点的 深度 为 0如果某一节点的深度为 d那它的子节点的深度就是 d1如果我们假定 A 是一组节点 S 的 最近公共祖先S 中的每个节点都在以 A 为根节点的子树中且 A 的深度达到此条件下可能的最大值。
示例 1
输入root [3,5,1,6,2,0,8,null,null,7,4]
输出[2,7,4]
解释我们返回值为 2 的节点在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意节点 6、0 和 8 也是叶节点但是它们的深度是 2 而节点 7 和 4 的深度是 3 。示例 2
输入root [1]
输出[1]
解释根节点是树中最深的节点它是它本身的最近公共祖先。示例 3
输入root [0,1,3,null,2]
输出[2]
解释树中最深的叶节点是 2 最近公共祖先是它自己。提示
树中的节点数将在 [1, 1000] 的范围内。0 Node.val 1000每个节点的值都是 独一无二 的。
注意 本题与力扣 865 重复https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/ 解法1 递归 看上图示例 1这棵树的节点 3 , 5 , 2 3,5,2 3,5,2 都是最深叶节点 7 , 4 7,4 7,4 的公共祖先但只有节点 2 2 2 是最近的公共祖先。
如果我们要找的节点只在左子树中那么最近公共祖先也必然只在左子树中。对于本题如果左子树的最大深度比右子树的大那么最深叶结点就只在左子树中所以最近公共祖先也只在左子树中。反过来说如果右子树的最大深度大于左子树那么最深叶结点就只在右子树中所以最近公共祖先也只在右子树中。
如果左右子树的最大深度一样呢当前节点一定是最近公共祖先吗不一定。比如节点 1 1 1 的左右子树最深叶节点 0 , 8 0,8 0,8 的深度都是 2 2 2 但该深度并不是全局最大深度所以节点 1 1 1 并不能是答案。
根据以上讨论正确做法如下
递归这棵二叉树同时维护全局最大深度 maxDepth \textit{maxDepth} maxDepth 。在「递」的时候往下传 d e p t h depth depth 用来表示当前节点的深度。在「归」的时候往上传当前子树最深叶节点的深度。设左子树最深叶节点的深度为 leftMaxDepth \textit{leftMaxDepth} leftMaxDepth 右子树最深叶节点的深度为 rightMaxDepth \textit{rightMaxDepth} rightMaxDepth 。如果 leftMaxDepth rightMaxDepth maxDepth \textit{leftMaxDepth}\textit{rightMaxDepth}\textit{maxDepth} leftMaxDepthrightMaxDepthmaxDepth 那么更新答案为当前节点。注意这并不代表我们找到了答案如果后面发现了更深的叶节点那么答案还会更新。
class Solution {
public:TreeNode *lcaDeepestLeaves(TreeNode *root) {TreeNode *ans nullptr;int max_depth -1; // 全局最大深度functionint(TreeNode*, int) dfs [](TreeNode *node, int depth) {if (node nullptr) {max_depth max(max_depth, depth); // 维护全局最大深度return depth;}int left_max_depth dfs(node-left, depth 1); // 获取左子树最深叶节点的深度int right_max_depth dfs(node-right, depth 1); // 获取右子树最深叶节点的深度if (left_max_depth right_max_depth left_max_depth max_depth)ans node;return max(left_max_depth, right_max_depth); // 当前子树最深叶节点的深度};dfs(root, 0);return ans;}
};复杂度分析
时间复杂度 O ( n ) \mathcal{O}(n) O(n) 。每个节点都会恰好访问一次。空间复杂度 O ( n ) \mathcal{O}(n) O(n) 。最坏情况下二叉树是一条链递归需要 O(n)\mathcal{O}(n)O(n) 的栈空间。 解法2 自底向上
也可以不用全局变量而是把每棵子树都看成是一个「子问题」即对于每棵子树我们需要知道
这棵子树最深叶结点的深度。这里是指叶子在这棵子树内的深度而不是在整棵二叉树的视角下的深度。相当于这棵子树的高度。这棵子树的最深叶结点的最近公共祖先 lca \textit{lca} lca 。
分类讨论
设子树的根节点为 n o d e node node n o d e node node 的左子树的高度为 leftHeight \textit{leftHeight} leftHeight n o d e node node 的右子树的高度为 rightHeight \textit{rightHeight} rightHeight 。如果 l e f t H e i g h t r i g h t H e i g h t leftHeightrightHeight leftHeightrightHeight 那么子树的高度为 leftHeight 1 \textit{leftHeight} 1 leftHeight1 lca \textit{lca} lca 是左子树的 lca \textit{lca} lca 。如果 leftHeight rightHeight \textit{leftHeight} \textit{rightHeight} leftHeightrightHeight 那么子树的高度为 r i g h t H e i g h t 1 rightHeight1 rightHeight1 l c a lca lca 是右子树的 l c a lca lca 。如果 leftHeight rightHeight \textit{leftHeight} \textit{rightHeight} leftHeightrightHeight 那么子树的高度为 leftHeight 1 \textit{leftHeight} 1 leftHeight1 l c a lca lca 就是 n o d e node node 。反证法如果 l c a lca lca 在左子树中那么 l c a lca lca 不是右子树的最深叶结点的祖先这不对如果 l c a lca lca 在右子树中那么 l c a lca lca 不是左子树的最深叶结点的祖先这也不对如果 l c a lca lca 在 n o d e node node 的上面那就不符合「最近」的要求。所以 l c a lca lca 只能是 n o d e node node。
class Solution {pairint, TreeNode* dfs(TreeNode *node) {if (node nullptr)return {0, nullptr};auto [left_height, left_lca] dfs(node-left);auto [right_height, right_lca] dfs(node-right);if (left_height right_height) // 左子树更高return {left_height 1, left_lca};if (left_height right_height) // 右子树更高return {right_height 1, right_lca};return {left_height 1, node}; // 一样高}public:TreeNode *lcaDeepestLeaves(TreeNode *root) {return dfs(root).second;}
};复杂度分析
时间复杂度 O ( n ) \mathcal{O}(n) O(n) 。每个节点都会恰好访问一次。空间复杂度 O ( n ) \mathcal{O}(n) O(n) 。最坏情况下二叉树是一条链递归需要 O ( n ) \mathcal{O}(n) O(n) 的栈空间。
更简洁的写法是
class Solution {
public:int depth[1010];TreeNode* lcaDeepestLeaves(TreeNode* root) {if (root nullptr) return nullptr;TreeNode* left root-left, *right root-right;TreeNode* lcaLeft lcaDeepestLeaves(root-left), *lcaRight lcaDeepestLeaves(root-right);int dl left ? depth[left-val] : 0, dr right ? depth[right-val] : 0;depth[root-val] max(dl, dr) 1;if (dl dr) return lcaLeft;if (dr dl) return lcaRight;return root;}
};
