题目描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

注：本题保证二叉树中每个节点的val值均不相同。

如当输入[3,5,1,6,2,0,8,#,#,7,4],5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。 节点本身可以视为自己的祖先

示例 1

输入: [3,5,1,6,2,0,8,#,#,7,4],5,1

输出: 3 

示例 2

输入: {}

输出: true

思路 & 解答

其实在前面的 68 题中，我们已经尝试过在普通二叉树查找节点的最近公共祖先。

我们不能直接判断出它在左子树，还是在右子树。不如暴力点，先在左子树中找，如果右子树没找到，说明都在左子树，如果左子树没找到，说明都在右子树，如果两个在左右子树中分别存在，说明当前节点就是他们的父节点。

Java 代码如下：

public class Solution86 {

    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        TreeNode result = commonAncestor(root, p, q);
        return result == null ? -1 : result.val;
    }

    public TreeNode commonAncestor(TreeNode root, int p, int q) {
        if (null == root) {
            return null;
        }
        if (root.val == p || root.val == q) {
            return root;
        }
        TreeNode left = commonAncestor(root.left, p, q);
        TreeNode right = commonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}

C++ 代码如下：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int lowestCommonAncestor(TreeNode *root, int p, int q) {
        TreeNode *result = commonAncestor(root, p, q);
        return result == NULL ? -1 : result->val;
    }


    TreeNode *commonAncestor(TreeNode *root, int p, int q) {
        // 等于空
        if (root == NULL) {
            return NULL;
        }
        if (root->val == p || root->val == q) {
            // 有一个值等于根节点
            return root;
        }
        TreeNode* left = commonAncestor(root->left, p, q);
        TreeNode* right = commonAncestor(root->right, p, q);
        if (left == NULL) {
            return right;
        } else if (right == NULL) {
            return left;
        } else {
            return root;
        }
    }
};

时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点访问一遍 空间复杂度：O（n），递归取决于栈的深度，最差情况下，二叉树退化成链表，栈的深度是n。