235. Lowest Common Ancestor of a Binary Search Tree

[Shawngbk]

如果这个二叉树是BST，那么我们可以利用BST的特点，把根节点的值与两个节点的值进行比较，如果两个节点的值都比根节点的值小，那么一定在根节点的左边，所以我们把根节点的左子节点作为起始点，然后递归。如果两个节点的值都比祖先节点的值大，那么一定在根节点的右边，所以我们把根节点的右子节点作为起始点，然后递归，如果上面两张情况都不是，那么很明显，这个根节点就是LCA http://blog.csdn.net/beiyetengqing/article/details/7633651 http://blog.csdn.net/xudli/article/details/46838747 /**

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

• } */ public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || p == null || q == null) return null; if(Math.max(p.val, q.val) < root.val) { return lowestCommonAncestor(root.left, p, q); } else if(Math.min(p.val, q.val) > root.val) { return lowestCommonAncestor(root.right, p, q); } else { return root; }

  } }