signed

QiShunwang

“诚信为本、客户至上”

【剑指offer】68.2 二叉搜索树的最近公共祖先

2021/3/21 10:09:27   来源:

题目描述

在这里插入图片描述

// 68.2 二叉搜索树的最近公共祖先


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

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

// 例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

题解

// 力扣
// 还记得《68. 二叉搜索树的最近公共祖先》,本题是68的一般情况,
// 因此可以本题的解可以用于68。
//
// 根据p和q的情况可以分成:
// 1.p和q不在同一个子树中,则公共祖先存在于p和q的父结点以上,且公共祖先
// 一定是p和q所在子树分支的根结点。
// 2.p在q的左/右子树中,公共祖先就是q,
// 3.q在p的左/右子树中,公共祖先就是p。
// 
// 遍历节点为root,递归终止条件为当root==null,或遍历节点到了p,
// 或遍历节点到了q时,返回root。root==null,说明遍历到了尽头,没有遇到
// p和q。当遇到p和q时,再往深遍历是不可能遇到公共祖先的,直接返回root。
//
// 递归调用主函数,输入为遍历节点root的左子树root.left,得到节点left。
// 递归调用主函数,输入为遍历节点root的右子树root.right,得到节点right。
// 如此递归树的左右每一个节点,如果得到的left==null,返回right,
// 如果得到的right==null,返回left。最终主函数返回root。
// 
// 执行用时:7 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗:39.9 MB, 在所有 Java 提交中击败了56.35%的用户
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root)
			return root;
		TreeNode left = lowestCommonAncestor(root.left, p, q);
		TreeNode right = lowestCommonAncestor(root.right, p, q);
		if (left == null)
			return right;
		else if (right == null)
			return left;
		return root;
    }
}