来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

说明:

  • 所有节点的值都是唯一的。

  • p、q 为不同节点且均存在于给定的二叉搜索树中。

    题解

    递归

    1. /**
    2. * Definition for a binary tree node.
    3. * public class TreeNode {
    4. *     int val;
    5. *     TreeNode left;
    6. *     TreeNode right;
    7. *     TreeNode(int x) { val = x; }
    8. * }
    9. */
    10. class Solution {
    11.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    12.       int parentVal = root.val;
    13.       int pVal = p.val;
    14.       int qVal = q.val;
    16.       if (pVal > parentVal && qVal > parentVal) {
    17.           return lowestCommonAncestor(root.right, p, q);
    18.       } else if (pVal < parentVal && qVal < parentVal) {
    19.           return lowestCommonAncestor(root.left, p, q);
    20.       } else {
    21.           return root;
    22.       }
    23.   }
    24. }

    复杂度分析

  • 时间复杂度：235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图1，其中235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图2为BST中节点的个数，在最坏的情况下我们可能需要遍历BST中所有的节点。

  • 空间复杂度：235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图3，所需开辟的额外空间主要是递归栈产生的，之所以是235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图4是因为BST的高度为235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图5。

迭代

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  12.         int pVal = p.val;
  13.         int qVal = q.val;
  14.         TreeNode node = root;
  15.         while (node != null) {
  16.             int parentVal = node.val;
  17.             if (pVal > parentVal && qVal > parentVal) {
  18.                 node = node.right;
  19.             } else if (pVal < parentVal && qVal < parentVal) {
  20.                 node = node.left;
  21.             } else {
  22.                 return node;
  23.             }
  24.         }
  26.         return null;
  27.     }
  28. }

复杂度分析

  • 时间复杂度：235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图6，其中235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图7为BST中节点的个数，在最坏的情况下我们可能需要遍历BST中所有的节点。
  • 空间复杂度：235. 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree) - 图8