0236. Lowest Common Ancestor of a Binary Tree

题目信息

题号:

0236

难度:

Medium

主题:

二叉树、最近公共祖先、深度优先搜索

原题:

LeetCode 0236

重点:

普通二叉树没有值序关系、返回原节点、祖先允许包含自身、两节点保证存在

题目重述

给定一棵普通二叉树的根节点 root,以及树中两个不同节点 p、q,返回它们的最近公共祖先。公共祖先必须同时位于 p 和 q 的祖先链上,最近公共祖先是其中深度最大的节点。按照题目定义,一个节点可以是它自己的祖先。

树中节点数位于 [2, 10^5],节点值位于 [-10^9, 10^9] 且互不相同。题目保证 p、q 都存在于树中并且二者不同。返回值必须是原树中的节点引用;普通二叉树不保证左子树值更小或右子树值更大,不能借用二叉搜索树的值序关系。输入树无需修改。

自建示例

两个节点来自不同分支:

输入:root = [9, 4, 13, 2, 6, 11, 15, null, 3],p = 节点 3,q = 节点 11
输出:节点 9
解释:3 位于根的左子树,11 位于根的右子树;节点 9 是首个同时包含两者的祖先。

其中一个节点是另一个的祖先:

输入:root = [7, 2, 8, 1, 5, null, 9],p = 节点 2,q = 节点 5
输出:节点 2
解释:节点 2 是节点 5 的祖先,同时也可作为自己的祖先,所以最近公共祖先是 2。

后序合并两侧信息

普通二叉树没有值序关系,必须从子树搜索。递归函数返回:当前子树中找到的 p 或 q 节点, 或者已经确定的最近公共祖先。对当前节点:

  • 当前节点为空,返回空;

  • 当前节点等于 p 或 q,直接返回当前节点;

  • 递归左右子树;

  • 左右都非空,说明两个目标分别在两侧,当前节点是最近公共祖先;

  • 只有一侧非空,返回那一侧继续向上;两侧都空则返回空。

命中目标后直接返回的含义是:若目标是另一个目标的祖先,目标节点应优先成为答案, 上层收到它后不会错误地用更高节点替代。

正确性说明

对每棵子树归纳。递归返回非空时,要么它是该子树唯一找到的目标,要么已经是该子树内同时覆盖两者的最近祖先。 当左右结果同时非空,两个目标分属当前节点两侧,任何更深节点只能位于一侧,当前节点就是最近公共祖先; 当只有一侧非空,另一目标若存在必在同一侧或当前节点已提前命中,返回该侧结果不会丢失更近答案。 题目保证目标存在,因此根调用返回的非空节点就是全树最近公共祖先。

C++ 实现

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root,
                                   TreeNode* p,
                                   TreeNode* q) {
        if (root == nullptr || root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left != nullptr && right != nullptr) return root;
        return left != nullptr ? left : right;
    }
};

代码分析

每个节点最多访问一次,时间复杂度为 O(n);递归栈空间为 O(h),其中 h 是树高。 比较使用节点指针而非节点值,因而即使值不唯一也能表达“目标节点身份”;本题输入保证两个目标确实存在, 不需要额外记录找到标记或修改树。