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`` 都存在于树中并且二者不同。返回值必须是原树中的节点引用;普通二叉树不保证左子树值更小或右子树值更大,不能借用二叉搜索树的值序关系。输入树无需修改。 自建示例 -------- 两个节点来自不同分支: .. code-block:: text 输入:root = [9, 4, 13, 2, 6, 11, 15, null, 3],p = 节点 3,q = 节点 11 输出:节点 9 解释:3 位于根的左子树,11 位于根的右子树;节点 9 是首个同时包含两者的祖先。 其中一个节点是另一个的祖先: .. code-block:: text 输入:root = [7, 2, 8, 1, 5, null, 9],p = 节点 2,q = 节点 5 输出:节点 2 解释:节点 2 是节点 5 的祖先,同时也可作为自己的祖先,所以最近公共祖先是 2。 后序合并两侧信息 ---------------- 普通二叉树没有值序关系,必须从子树搜索。递归函数返回:当前子树中找到的 ``p`` 或 ``q`` 节点, 或者已经确定的最近公共祖先。对当前节点: * 当前节点为空,返回空; * 当前节点等于 ``p`` 或 ``q``,直接返回当前节点; * 递归左右子树; * 左右都非空,说明两个目标分别在两侧,当前节点是最近公共祖先; * 只有一侧非空,返回那一侧继续向上;两侧都空则返回空。 命中目标后直接返回的含义是:若目标是另一个目标的祖先,目标节点应优先成为答案, 上层收到它后不会错误地用更高节点替代。 正确性说明 ---------- 对每棵子树归纳。递归返回非空时,要么它是该子树唯一找到的目标,要么已经是该子树内同时覆盖两者的最近祖先。 当左右结果同时非空,两个目标分属当前节点两侧,任何更深节点只能位于一侧,当前节点就是最近公共祖先; 当只有一侧非空,另一目标若存在必在同一侧或当前节点已提前命中,返回该侧结果不会丢失更近答案。 题目保证目标存在,因此根调用返回的非空节点就是全树最近公共祖先。 C++ 实现 -------- .. code-block:: cpp 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`` 是树高。 比较使用节点指针而非节点值,因而即使值不唯一也能表达“目标节点身份”;本题输入保证两个目标确实存在, 不需要额外记录找到标记或修改树。