最深叶节点的最近公共祖先【LC1123】
给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。
回想一下：
叶节点 是二叉树中没有子节点的节点
树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
递归
- 思路
- 假设最深叶节点的深度为
maxDepth，那么如果某个节点左右子树的深度均等于maxDepth，那么更新答案为该节点。 - 注意：递归过程中，上层父节点最后处理，因此如果左右子树都存在最深叶节点，会覆盖之前的答案
- 实现
class Solution { int maxDepth = 0; TreeNode res = null; public TreeNode lcaDeepestLeaves(TreeNode root) { dfs(root, 0); return res; } public int dfs(TreeNode root, int depth){ if (root == null) return depth; int l = dfs(root.left, depth + 1); int r = dfs(root.right, depth + 1); maxDepth = Math.max(depth + 1, maxDepth); if (l == maxDepth && r == maxDepth){ res = root; } return Math.max(l, r); } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
自底向上
- 思路
寻找子问题：每棵树的「最深叶结点的最近公共祖先lca」与其左右子树的高度相关
该问题是一个重复的子问题，因此可以使用递归解决，返回值设置为子树高度及子树的lca
实现
class Solution { public TreeNode lcaDeepestLeaves(TreeNode root) { return dfs(root).getValue(); } private Pair<Integer, TreeNode> dfs(TreeNode node) { if (node == null) return new Pair<>(0, null); var left = dfs(node.left); var right = dfs(node.right); if (left.getKey() > right.getKey()) // 左子树更高 return new Pair<>(left.getKey() + 1, left.getValue()); if (left.getKey() < right.getKey()) // 右子树更高 return new Pair<>(right.getKey() + 1, right.getValue()); return new Pair<>(left.getKey() + 1, node); // 一样高 } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/solutions/2428724/liang-chong-di-gui-si-lu-pythonjavacgojs-xxnk/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
