P139 二叉搜索树中节点的最近公共祖先

描述#

这个题目说的是，给你一棵二叉搜索树以及树中两个节点，你要找到这两个节点的最近公共祖先，然后将它返回。注意，树上所有的节点值都不相同。

比如说，给你的二叉搜索树为：
  4
/   \

2     5
/ \     

1   3     6
节点 1 和 3 的最近公共祖先是节点 2；
节点 3 和 6 的最近公共祖先是节点 4；
节点 4 和 6 的最近公共祖先也是节点 4。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(h), Space: O(h)
  public TreeNode lcaRecursive(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val)
      return lcaRecursive(root.left, p, q);
    else if (p.val > root.val && q.val > root.val)
      return lcaRecursive(root.right, p, q);
    else return root;
  }

  // Time: O(h), Space: O(1)
  public TreeNode lcaIterative(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
      if (p.val < root.val && q.val < root.val) root = root.left;
      else if (p.val > root.val && q.val > root.val) root = root.right;
      else return root;
    }
    return null;
  }

}