剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

image.png

递归法

  1. public class Solution {
  3.     /**
  4.      * 因为是二叉搜索树，所以可以使用其特性快速找到结果
  5.      * 如果两个节点都在 root 的左边，就往左走一步
  6.      * 如果两个节点都在 root 的右边，就往右走一步
  7.      * 如果两个节点分别在 root 左边和右边，直接返回 root
  8.      */
  9.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  10.         if (p.val < root.val && q.val < root.val) {
  11.             return lowestCommonAncestor(root.left, p, q);
  12.         } else if (p.val > root.val && q.val > root.val) {
  13.             return lowestCommonAncestor(root.right, p, q);
  14.         }
  15.         return root;
  16.     }
  17. }

迭代法

  1. public class Solution {
  3.     /**
  4.      * 因为是二叉搜索树，所以可以使用其特性快速找到结果
  5.      * 如果两个节点都在 root 的左边，就往左走一步
  6.      * 如果两个节点都在 root 的右边，就往右走一步
  7.      * 如果两个节点分别在 root 左边和右边，直接返回 root
  8.      */
  9.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  10.         while(true) {
  11.             if (p.val < root.val && q.val < root.val) {
  12.                 root = root.left;
  13.             } else if (p.val > root.val && q.val > root.val) {
  14.                 root = root.right;
  15.             } else {
  16.                 break;
  17.             }
  18.         }
  19.         return root;
  20.     }
  21. }