Problem: 236. 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

首先我们要注意到题目所给提示**二叉树的所有节点值均不相等！！！**在此基础上我们可以得到二叉树的最近公共祖先的唯一存在如下两种情况：

1.若当前节点的左子树和右子树均存在给定节点的其一，则当前节点为最近公共祖先；
2.若当前节点等于所给节点的其中一个，同时当前节点的左子树或者右子树中存在所给节点的另一个节点，则当前节点为最近公共祖先

如下图示：

解题方法

1.定义一个TreeNode类型的指针命名为location用于记录并返回最后的最近公共祖先
2.递归后续遍历二叉树，记录当前节点（包括当前节点）的左子树或右子树节点等于给定节点的个数
3.判断当前节点是否等于给定节点中其一，同时其左右子树中等于给定节点的个数（具体的判定条件看思路）判定成立时将指针location指向当前节点。
4.注意若在递归过程中发现指针location已经不为null则直接退出递归

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //用于记录指定节点最近的父节点位置
    private TreeNode location = null;
   /**
     * 求取二叉树中指定两节点的最近公共父节点（二叉树任意节点值无重复）
     *
     * @param root 树的根节点
     * @param p    指定节点p
     * @param q    指定节点q
     * @return TreeNode
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        depthFirstSearch(root, p, q);
        return location;
    }

    /**
     * 深度优先（此处为二叉树的后序遍历）求取某一节点指定的
     * 节点p 与 q的个数，利用其找到最近父节点的位置
     * @param root 树的根节点
     * @param p    指定节点p
     * @param q    指定节点q
     * @return int
     */
    private int depthFirstSearch(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }
        //当前节点左子树包含p，q节点的个数
        int leftContains = depthFirstSearch(root.left, p, q);
        //当已经找到location时提前退出
        if (location != null) {
            return 2;
        }
        //当前节点右子树包含p，q节点的个数
        int rightContains = depthFirstSearch(root.right, p, q);
        if (location != null) {
            return 2;
        }
        //记录当前节点值等于q或p
        int rootContain = 0;
        //如果当前节点值等于p，q其一
        if (root == p || root == q) {
            rootContain = 1;
        }
        /*
        找到情况1：当当前节点值等于p，q其一时，同时当前节点的左子树
                 或右子树包含q，p的个数为1
        找到情况2：当当前节点的左子树包含一个p或q其一，同时当前节点
                 的右子树包含一个q或p其一
         */
        if (rootContain == 1 && (leftContains == 1 || rightContains == 1)) {
            location = root;
        }
        if (rootContain == 0 && leftContains == 1 && rightContains == 1) {
            location = root;
        }
        return leftContains + rightContains + rootContain;
    }
}