初学者友好指南《Smallest Subtree with all the Deepest Nodes》 – LeetCode 865 (C++, Python, JavaScript)

Source: Dev.to

问题概要

给定：

• 二叉树的 root（根节点）。
• 各层的节点，其中“最深”节点是指离根节点最远的节点。

目标：

• 找到包含所有最深节点的最小子树。如果只有一个最深节点，则该节点本身即为答案。

直觉

要解决这个问题，我们需要了解每个节点的两件事：它的后代有多深？以及哪个节点是它们的公共祖先？

我们使用递归的深度优先搜索（DFS）方法。函数不只返回单个值，而是返回一对值：该子树中达到的最深层级以及最近公共祖先（LCA）的候选节点。

• 基准情况（Base Case）： 如果节点为 null，其深度为 0，且不存在 LCA。
• 递归步骤（Recursive Step）： 查询左、右子节点的最大深度。
  • 如果 左侧更深，则最深的节点仅在左子树中；向上传播左侧的结果。
  • 如果 右侧更深，则最深的节点仅在右子树中；向上传播右侧的结果。
  • 如果 深度相等，最深的节点分布在左、右两个分支中，此时当前节点是将它们连接起来的最小子树。

代码块

C++

struct Result {
    TreeNode* lca;
    int depth;
};

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).lca;
    }

private:
    Result dfs(TreeNode* root) {
        if (root == nullptr) return {nullptr, 0};

        Result left = dfs(root->left);
        Result right = dfs(root->right);

        // If one side is deeper, the deepest nodes are exclusively there
        if (left.depth > right.depth) {
            return {left.lca, left.depth + 1};
        }
        if (left.depth  // truncated line from original source

Python

class Solution:
    def subtreeWithAllDeepest(self, root):
        def dfs(node):
            if not node:
                return None, 0

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

            if left_depth > right_depth:
                return left_lca, left_depth + 1
            if right_depth > left_depth:
                return right_lca, right_depth + 1

            # If depths are equal, current node is the LCA
            return node, left_depth + 1

        return dfs(root)[0]

JavaScript

var subtreeWithAllDeepest = function(root) {
    const dfs = (node) => {
        if (!node) return { lca: null, depth: 0 };

        const left = dfs(node.left);
        const right = dfs(node.right);

        if (left.depth > right.depth) {
            return { lca: left.lca, depth: left.depth + 1 };
        }
        if (right.depth > left.depth) {
            return { lca: right.lca, depth: right.depth + 1 };
        }

        // If depths are equal, this node is the common ancestor
        return { lca: node, depth: left.depth + 1 };
    };

    return dfs(root).lca;
};

关键要点

• 后序遍历: 在处理父节点之前先处理子节点，允许基于完整子树信息做决定。
• 多返回值: 同时返回节点和深度可避免冗余遍历，使算法保持高效。
• 最近公共祖先逻辑: 该问题是经典最近公共祖先问题的变体，其中“目标”由深度动态定义，而不是具体值。

最后思考

这个问题在技术面试中很受欢迎，因为它考察了你处理递归和复杂返回类型的能力。实际上，这一逻辑类似于在数据库层次结构中寻找“最具体的公共类别”，或在复杂的依赖树中识别最小的共享组件。掌握这种自下而上的信息流对于处理层次数据的工程师来说至关重要。