LCA of BST

描述

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

  1.       _______6______
  2.        /              \
  3.     ___2__          ___8__
  4.    /      \        /      \
  5.    1      _4       7       9
  6.          /  \
  7.          3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

分析

根据二叉搜索树的性质，两个子节点p,q和根节点root的关系，有以下四种情况：

  • 两个子节点都在树的左子树上
  • 两个子节点都在树的右子树上
  • 一个子节点在左子树，一个子节点在右子树
  • 一个子节点的值和根节点的值相等
    以题目中的树为例，节点1和节点4为情况1，节点7和节点9为情况2，节点1和节点7为情况3，节点2和4为情况4。若为情况3或4，当前节点即为最近公共祖先，若为情况1或2，则还需递归到左或右子树上，继续这个过程。

该算法的时间复杂度为O(h)，h为树的高度。

解法1 递归

  1. // LCA of BST
  2. // Time Complexity: O(h), Space Complexity: O(h)
  3. public class Solution {
  4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  5.         if (root == null) return null;
  7.         if (Math.max(p.val, q.val) < root.val) {
  8.             return lowestCommonAncestor(root.left, p, q);
  9.         } else if (Math.min(p.val, q.val) > root.val) {
  10.             return lowestCommonAncestor(root.right, p, q);
  11.         } else {
  12.             return root;
  13.         }
  14.     }
  15. }

解法2 迭代

  1. // LCA of BST
  2. // Time Complexity: O(h), Space Complexity: O(1)
  3. public class Solution {
  4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  5.         while (root != null) {
  6.             if (Math.max(p.val, q.val) < root.val) {
  7.                 root = root.left;
  8.             } else if (Math.min(p.val, q.val) > root.val) {
  9.                 root = root.right;
  10.             } else {
  11.                 return root;
  12.             }
  13.         }
  14.         return null;
  15.     }
  16. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/bst/lca-of-bst.html