leetcode

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

Problem

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

1. 题目简述

给出一棵BST树，给出其两个节点p和q，找出p和q的高度最低公共ancestor节点，本身也是自己的祖先节点。例如：

平衡二叉树

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

2. 算法思路

BST树的特性

这道题和LeetCode 236看起来很像，但是做法其实完全不同，本题为easy，用到BST树的特性秒解。

对于任意一个节点，其左子树的所有值必定小于其右子树的值。我们假设p.val < q.val。因此，对于某节点n，如果n.val < p.val < q.val，则p和q一定都在其右子树，左子树可以全部剪枝；p.val < q.val < n.val，则p和q一定都在其左子树，右子树可以全部剪枝；如果p和q分别在其左子树和右子树上，则它就是那个高度最低的公共祖先节点。

3. 解法

  1. 利用BST数的节点特性

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode lowestAncestor;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while ((p.val - root.val) * (q.val - root.val) > 0) {
            if (p.val < root.val) {
                // p和q都在左子树
                root = root.left;
            } else {
                root = root.right;
            }
        }

        return root;
    }
}