LeetCode 236 [Lowest Common Ancestor of a Binary Tree]

题目链接

题目描述

  • 给定一颗二叉树,查找两个结点的最近公共祖先。最近公共祖先的定义:二叉树里面同时拥有两个给定后代结点的高度最低的结点,一个结点可以作为它自己的祖先结点。

解题思路

  • 一开始的思路

    • 只要根结点不为NULL,那么它肯定是任意两个结点的公共祖先。从根结点出发到达两个给定结点,可以得到两条路径(类似链表),这两条路径的起始结点都是根结点,沿着路径逐个对比,它们最后一个公共结点就是待查找的最近公共祖先。实际处理的时候,不需要以链表的方式生成一条路径,我的想法是使用包含bool元素的vector记录每次向左还是向右走,这样也可以表示路径信息。
    • 这种方法的问题在于需要使用额外的存储来记录路径信息,在计算资源足够的情况下,这种方式可以得到结果,但本题的一个测试用例包含约10000个结点,测试时直接报”Runtime Error”,因此这种思路不能作为本题的正确解法。
  • 参考别人的思路

    • Solutions里看到别人发表的非常简洁的递归解法,只有4行,真的非常精妙,并且不需要额外的变量存储空间。
    • 这种解法的思路如下:
      1. 把根结点作为当前结点,查找以当前结点为根的树。查找结果可以分为四种:
        1. 两个给定结点都在当前的树里
        2. 只有第一个结点在当前的树里
        3. 只有第二个结点在当前的树里
        4. 两个给定结点都不在当前的树里
      2. 如果当前结点为NULL,则表示查找结果为上述第四种,返回NULL;如果当前结点是给定的第一个结点,则表示查找结果为上述第二种,返回当前结点;如果当前结点是给定的第二个结点,则表示查找结果为上述第三种,返回当前结点;如果前面几种情况都不满足,那么就需要查找它的左右子树了,左右子树的查找规则跟本步骤一模一样,查找结果同样可以分为四种:
        1. 在左子树中找到了一个给定结点,左子树查找结果不为NULL;在右子树中也找到了一个给定结点,右子树查找结果不为NULL。这种情况说明最近公共祖先就是当前结点(左右子树的父结点),返回当前结点
        2. 在左子树中找到了一个或两个给定结点,左子树查找结果不为NULL;在右子树中没有找到给定结点,右子树查找结果为NULL。这种情况说明最近公共祖先必然在当前结点上方,返回左子树查找结果
        3. 在右子树中找到了一个或两个给定结点,右子树查找结果不为NULL;在左子树中没有找到给定结点,左子树查找结果为NULL。这种情况说明最近公共祖先必然在当前结点上方,返回右子树查找结果
        4. 在左右子树中都没有找到给定结点,查找结果都为NULL。这种情况说明当前的树不包含任何指定结点,返回NULL
      3. 上一步骤的四种查找结果中,第2和第3种都需要返回子树的查找结果,而不是返回当前结点的处理结果,否则会导致最终找到的都是根结点

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return left && right ? root : left ? left : right ? right : NULL;
}
};