LeetCode 236 [Lowest Common Ancestor of a Binary Tree]

题目链接

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

题目描述

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

解题思路

一开始的思路：
1. 只要根结点不为NULL，那么它肯定是任意两个结点的公共祖先。从根结点出发到达两个给定结点，可以得到两条路径（类似链表），这两条路径的起始结点都是根结点，沿着路径逐个对比，它们最后一个公共结点就是待查找的最近公共祖先。实际处理的时候，不需要以链表的方式生成一条路径，我的想法是使用包含bool元素的vector记录每次向左还是向右走，这样也可以表示路径信息。
2. 这种方法的问题在于需要使用额外的存储来记录路径信息，在计算资源足够的情况下，这种方式可以得到结果，但本题的一个测试用例包含约10000个结点，测试时直接报”Runtime Error”，因此这种思路不能作为本题的正确解法。
参考别人的思路：
1. 在Solutions里看到别人发表的非常简洁的递归解法，只有4行，真的非常精妙，并且不需要额外的变量存储空间。
2. 这种解法的思路如下：
  1. 把根结点作为当前结点，查找以当前结点为根的树。查找结果可以分为四种：
    1. 两个给定结点都在当前的树里。
    2. 只有第一个结点在当前的树里。
    3. 只有第二个结点在当前的树里。
    4. 两个给定结点都不在当前的树里。
  2. 如果当前结点为NULL，则表示查找结果为上述第四种，返回NULL；如果当前结点是给定的第一个结点，则表示查找结果为上述第二种，返回当前结点；如果当前结点是给定的第二个结点，则表示查找结果为上述第三种，返回当前结点；如果前面几种情况都不满足，那么就需要查找它的左右子树了，左右子树的查找规则跟本步骤一模一样，查找结果同样可以分为四种：
    1. 在左子树中找到了一个给定结点，左子树查找结果不为NULL；在右子树中也找到了一个给定结点，右子树查找结果不为NULL。这种情况说明最近公共祖先就是当前结点（左右子树的父结点），返回当前结点。
    2. 在左子树中找到了一个或两个给定结点，左子树查找结果不为NULL；在右子树中没有找到给定结点，右子树查找结果为NULL。这种情况说明最近公共祖先必然在当前结点上方，返回左子树查找结果。
    3. 在右子树中找到了一个或两个给定结点，右子树查找结果不为NULL；在左子树中没有找到给定结点，左子树查找结果为NULL。这种情况说明最近公共祖先必然在当前结点上方，返回右子树查找结果。
    4. 在左右子树中都没有找到给定结点，查找结果都为NULL。这种情况说明当前的树不包含任何指定结点，返回NULL。
  3. 上一步骤的四种查找结果中，第2和第3种都需要返回子树的查找结果，而不是返回当前结点的处理结果，否则会导致最终找到的都是根结点。

C++代码

/**
 * 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;
    }
};

Menu

题目链接

题目描述

解题思路

C++代码