package LeetCode;

public class LeetCode253 {

/// 235. Lowest Common Ancestor of a Binary Search Tree

/// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

/// 时间复杂度: O(lgn), 其中n为树的节点个数

/// 空间复杂度: O(h), 其中h为树的高度

// Definition for a binary tree node.

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (p == null || q == null)

throw new IllegalArgumentException("p or q can not be null.");

if (root == null)

return null;

// p q 都在root左边

if (p.val < root.val && q.val < root.val)

return lowestCommonAncestor(root.left, p, q);

// p q 都在root右边

if (p.val > root.val && q.val > root.val)

return lowestCommonAncestor(root.right, p, q);

assert p.val == root.val || q.val == root.val

|| (root.val - p.val) * (root.val - q.val) < 0;

// 某个节点是root，直接返回root

return root;

}

}