二叉搜索树的最近公共祖先

---

题目：

题解：

解题思路：

1、迭代

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 logN （满二叉树），最大为 N （退化为链表）。
  • 空间复杂度 O(1) ： 使用常数大小的额外空间。

• 代码：

  class Solution {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          while(root != null) {
              if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                  root = root.right; // 遍历至右子节点
              else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                  root = root.left; // 遍历至左子节点
              else break;
          }
          return root;
      }
  }

  优化：若可保证 p.val < q.val ，则在循环中可减少判断条件。

  class Solution {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          if(p.val > q.val) { // 保证 p.val < q.val
              TreeNode tmp = p;
              p = q;
              q = tmp;
          }
          while(root != null) {
              if(root.val < p.val) // p,q 都在 root 的右子树中
                  root = root.right; // 遍历至右子节点
              else if(root.val > q.val) // p,q 都在 root 的左子树中
                  root = root.left; // 遍历至左子节点
              else break;
          }
          return root;
      }
  }

2、递归

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 logN （满二叉树），最大为 N （退化为链表）。
  • 空间复杂度 O(N) ： 最差情况下，即树退化为链表时，递归深度达到树的层数 N 。

• 代码：

  class Solution {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          // 当 p, q 都在 root 的 左子树 中，则开启递归 root.left 并返回
          if (root.val > p.val && root.val > q.val) {
              return lowestCommonAncestor(root.left,p,q);
          }
          // 当 p, q 都在 root 的 右子树 中，则开启递归 root.right 并返回
          if (root.val < p.val && root.val < q.val) {
              return lowestCommonAncestor(root.right,p,q);
          }
          return root;
      }
  }