Solutions CS101

Appearance

M1123.最深叶节点的最近公共祖先 ​

dfs, https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

  • 叶节点 是二叉树中没有子节点的节点
  • 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
  • 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

示例 1：

img
输入：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、先找出所有的叶子节点，然后对比长度，在最长的节点的路径中，找到第一个大家出现分歧的位置，然后输出相应节点就可以了。2、注意对于二叉树，只需要存储在这个节点是选择了想做还是向右就可以了，同时因为在回溯之外操作了path，所以需要把操作pop掉。3、注意各种指标要不要加一或者减一。

python
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        paths=[]
        leaves=[]
        def backtracking(cur,level,path):
            if cur.left:
                path.append('left')
                backtracking(cur.left,level+1,path)
                path.pop()
            if cur.right:
                path.append('right')
                backtracking(cur.right,level+1,path)
                path.pop()
            if (not cur.left) and (not cur.right):
                paths.append(path[:])
                leaves.append(level)
        backtracking(root,0,[])
        max_level=max(leaves)
        ans=[]
        for i,p in enumerate(paths):
            if leaves[i]==max_level:
                ans.append(p)
        
        common=0
        for i in range(max_level):
            same=True
            for j in range(len(ans)):
                if ans[j][i]!=ans[0][i]:
                    same=False
                    break
            if not same:
                break
            common+=1
        go=ans[0]
        cur=root
        for i in range(common):
            if go[i]=='left':
                cur=cur.left
            else:
                cur=cur.right
        return cur

优化版本（O(n) 时间 + O(h) 空间）

更高效的做法是 一次 DFS 同时返回 (深度, 节点)，不用存路径。

优化思路

对于每个节点：

  • 递归得到左、右子树的最深深度与对应的“最近公共祖先”；
  • 比较左右深度：
    • 若左 > 右：返回左边结果；
    • 若右 > 左：返回右边结果；
    • 若左 == 右：返回当前节点（因为这是最深节点的公共祖先）。
python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                # 返回 (深度, LCA) 元组
                return (0, None)

            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)

            if left_depth > right_depth:
                # 更深的子树在左子树
                return (left_depth + 1, left_lca)
            elif right_depth > left_depth:
                # 更深的子树在右子树
                return (right_depth + 1, right_lca)
            else:
                # 左右子树深度相同，当前节点是LCA
                return (left_depth + 1, node)

        _, lca = dfs(root)
        return lca


# 辅助函数保持不变
def list_to_tree(lst, index=0):
    if index >= len(lst) or lst[index] is None:
        return None
    root = TreeNode(lst[index])
    root.left = list_to_tree(lst, 2 * index + 1)
    root.right = list_to_tree(lst, 2 * index + 2)
    return root


def tree_to_list(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    # 去除末尾的None
    while result and result[-1] is None:
        result.pop()
    return result


# 示例测试
if __name__ == "__main__":
    solution = Solution()

    # 示例 1
    root1 = list_to_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    lca1 = solution.lcaDeepestLeaves(root1)
    print(lca1.val)  # 输出应为2

    # 示例 2
    root2 = list_to_tree([1])
    lca2 = solution.lcaDeepestLeaves(root2)
    print(lca2.val)  # 输出应为1

    # 示例 3
    root3 = list_to_tree([0, 1, 3, None, 2])
    lca3 = solution.lcaDeepestLeaves(root3)
    print(lca3.val)  # 输出应为2

    # 额外测试
    # 构建一个更复杂的树进行测试
    #       1
    #      / \
    #     2   3
    #    / \
    #   4   5
    #      /
    #     6
    root4 = list_to_tree([1, 2, 3, 4, None, 5, None, 6])
    lca4 = solution.lcaDeepestLeaves(root4)
    print(lca4.val)

解释

递归函数 dfs：

  • 对于每个节点，递归地计算其左子树和右子树的深度及对应的 LCA。
  • 如果左子树比右子树深，返回左子树的深度加一以及左子树的 LCA。
  • 如果右子树比左子树深，返回右子树的深度加一以及右子树的 LCA。
  • 如果左右子树深度相同，当前节点就是最深叶节点的 LCA，返回当前深度加一以及当前节点。

复杂度分析

  • 时间复杂度：O(N)，其中 N 是树中的节点数。每个节点只被访问一次。
  • 空间复杂度：O(H)，其中 H 是树的高度。递归调用栈的深度取决于树的高度。

【赵凌哲 光华管理学院】思路：二进制标记每个节点，这样求最近公共祖先其实就是二进制的公共前缀。

python
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        dic = {}
        if root.left==None and root.right == None:
            return root
        def dfs(node, now):
            dic[now] = node
            if node.left:
                dfs(node.left, now<<1)
            if node.right:
                dfs(node.right, now<<1|1)
        dfs(root, 1)
        deep = sorted([x for x in dic.keys() if x.bit_length() == max(dic.keys()).bit_length()])
        if len(deep) == 1:
            return dic[deep[-1]]
        else:
            return dic[deep[0]>>((deep[0]^deep[-1]).bit_length())]

这个代码思路很“位运算味”，我们来一步步解读。

🧩 题目理解

题目：1123. 最深叶节点的最近公共祖先

给定一棵二叉树，找到所有最深叶节点的最近公共祖先（LCA）。

换句话说：

  • 先找到最深层（depth 最大）的所有叶子；
  • 再找这些叶子的最近公共祖先。

🧠 思路概述

这段代码用了一个很有创意的方法： 用二进制路径编码节点位置，然后通过二进制前缀来找公共祖先。

1️⃣ 二进制编码规则

  • 根节点记为 1
  • 左子树记为 now << 1
  • 右子树记为 now << 1 | 1

例如：

         1(1)
        /   \
   (10)2     3(11)
      / \     \
 (100)4 (101)5 (111)7

可以看到每一层的节点路径是二进制“左移 + 加 1”的扩展。

这其实相当于记录了每个节点在一棵完全二叉树中的“位置索引”。

2️⃣ 用字典存储路径 → 节点映射

python
dic[now] = node

DFS 遍历整棵树，把每个节点对应的二进制路径值存起来。

3️⃣ 找出最深层的叶子节点

python
max_depth = max(dic.keys()).bit_length()
deep = [x for x in dic if x.bit_length() == max_depth]

解释：

  • .bit_length() = 二进制位数 = 深度
  • 比如根是 1(1) → 深度1 左孩子 10 → 深度2 101 → 深度3
  • 所以最深节点就是“二进制长度最长”的那些节点。

4️⃣ 如果只有一个最深节点

那它自己就是最近公共祖先：

python
if len(deep) == 1:
    return dic[deep[-1]]

5️⃣ 否则有多个最深叶子 → 找它们的 LCA

关键语句：

python
return dic[deep[0] >> ((deep[0] ^ deep[-1]).bit_length())]

这句很巧妙，我们来逐步分解：

(1) deep[0] ^ deep[-1]

  • 按位异或找出两个路径第一个不同的位置；
  • 比如 100 (4) 和 101 (5)，异或得 001。

(2) .bit_length()

  • 这个结果的 bit_length 表示“从尾部向前，需要移掉多少位才能到公共前缀”。

(3) deep[0] >> k

  • 把路径右移 k 位，去掉不同的后缀；
  • 得到的就是最近公共祖先的路径编号。

举个例子 🌳

        1
       / \
      2   3
     / \
    4   5

路径编号：

1: 1
2: 10
3: 11
4: 100
5: 101

最深节点：4(100) 和 5(101) 异或：100 ^ 101 = 001 bit_length = 1 右移1位：100 >> 1 = 10 路径 10 对应节点 2 → 正是最近公共祖先 ✅

✅ 总结

步骤思路关键点
1DFS 遍历整棵树用二进制路径表示节点
2记录路径 → 节点映射dic[now] = node
3找最深节点（bit_length 最大）.bit_length() 表示深度
4若只有一个最深叶它自己就是 LCA
5否则用异或求公共前缀>> ((a^b).bit_length())

⚙️ 优点与不足

优点：

  • 位运算巧妙高效；
  • 不需要显式记录深度和父节点。

不足：

  • 依赖整数大小（若树太深可能超出 int 范围）；
  • 逻辑抽象，理解门槛高；
  • 不易推广到非完全二叉结构的遍历方式（如有指针变化的树）。

思路：自下向上递归，在最后的叶子结点的高度设置成0，之后对于其他的节点，记录下该节点的高度，并且判定是否高度是最高的，直到左右节点的高度一样，并且同为在当前层的最大高度，这个节点就是最后要输出的节点

python
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root):
            if root == None:
                return 0,None
            lefts,left_note = dfs(root.left)
            rights,right_note = dfs(root.right)
            if lefts > rights:
                return lefts+1,left_note
            elif lefts < rights:
                return rights+1,right_note
            return lefts+1,root
        return dfs(root)[1]

思路：记录先最大的深度，每次得到的左右子节点的深度相同时保留该节点，如果遇到有更深的节点，就对该节点更新，否则该节点就是我们要输出的节点

python
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        max_depth = -1
        ans = None
        def dfs(root,depth):
            nonlocal max_depth,ans
            if root == None:
                max_depth = max(depth,max_depth)
                return depth
            lefts = dfs(root.left,depth+1)
            rights = dfs(root.right,depth+1)
            if lefts == rights == max_depth:
                ans = root
            return max(lefts,rights)
        dfs(root,0)
        return ans