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

类型：树

• 235. 二叉搜索树的最近公共祖先 💛

  https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

  ❓ 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。（一个节点也可以是它自己的祖先。）

  💡 一次遍历

  此题与「236. 二叉树的最近公共祖先」的关键区别在于，这是一棵二叉搜索树。我们利用搜索树的性质，可以很快地找到目标。

  我们从根结点开始遍历：

  • 如果 p 和 q 的值小于当前结点，那么 p 和 q 应该都在当前结点的左子树中，我们继续向左子树遍历。
  • 如果 p 和 q 的值大于当前结点，那么 p 和 q 应该都在当前结点的右子树中，我们继续向右边子树遍历。
  • 如果不满足上述两种情况，说明当前结点就是分岔点，也就是咱们要找的最近公共祖先。此时 p 和 q 要么分别位于当前结点的左右子树当中，要么其中一个就是当前结点。

  class Solution:
      def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
          ancestor = root
          while True:
              if p.val < ancestor.val and q.val < ancestor.val:
                  ancestor = ancestor.left
              elif p.val > ancestor.val and q.val > ancestor.val:
                  ancestor = ancestor.right
              else:
                  break
          return ancestor

  时间复杂度：O(n)，空间复杂度：O(1)