二叉搜索树的最近公共祖先235.

需求

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

二叉搜索树

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

leetcode题目链接

思路

既然是二叉搜索树，那么这个提的解题思路是要利用到二叉搜索树的特点，任意元素节点>左子树节点，>右子树节点。
1.如果值小于两个需要寻找的叶子节点值，说明一定在左子树。
2.如果值大与两个需要寻找值的值，索命一定在右子树。
3.如果值在两个节点中间说明找了最近公共父节点。两个需要寻找的值一个在左子树一个在右子树说明此节点为第一个相交的父节点，第三点也是原子操作。

/**
 * 235. 二叉搜索树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
 */
public class LowestCommonAncestor235 {

    /**
     * 递归法
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 首次传入 或者遍历到叶子节点停止
        if (root == null) return null;

        // 左
        if (root.val > p.val && root.val > q.val) {// 说明在左子树
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if (left != null) return left;
        }

        // 右
        if (root.val < p.val && root.val < q.val) {// 说明在右子树
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (right != null) return right;
        }

        // root.val 在 p q 之间
        // pq之一，一定在root左子树 pqz之一，一定在右子树中
        // pq大小左右顺序忽略，可互换
        // 只要包含公共父节点，一定会是qp在公共节点的左右两侧，最后return一定执行
        return root;

    }

    /**
     * 层序遍历（广度遍历）
     */
    public TreeNode lowestCommonAncestorGd(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > p.val && cur.val > q.val) {
                cur = cur.left;
            } else if (cur.val < p.val && cur.val < q.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }
}

验证结果