携手创作，一起生长！这是我参加「日新方案 8 月更文挑战」的第23天，点击检查活动概况

题目

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

百度百科中最近公共先人的界说为：“关于有根树 T 的两个结点 p、q，最近公共先人表示为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也可以是它自己的先人）。”

例如，给定如下二叉查找树: root =[6,2,8,0,4,7,9,null,null,3,5]

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

示例 1：

  • 输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
  • 输出：6
  • 解说： 节点 2 和节点 8 的最近公共先人是 6。

示例 2：

  • 输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
  • 输出：2
  • 解说： 节点 2 和节点 4 的最近公共先人是 2, 由于依据界说最近公共先人节点可认为节点自身。

办法一：一次遍历

思路及解法

整体的遍历进程如下：

  • 我们从根节点开始遍历；

  • 假如当时节点的值大于 pp 和 qq 的值，阐明 pp 和 qq 应该在当时节点的左子树，因此将当时节点移动到它的左子节点；

  • 假如当时节点的值小于 pp 和 qq 的值，阐明 pp 和 qq 应该在当时节点的右子树，因此将当时节点移动到它的右子节点；

  • 假如当时节点的值不满足上述两条要求，那么阐明当时节点就是「分岔点」。此刻，pp 和 qq 要么在当时节点的不同的子树中，要么其间一个就是当时节点。

代码

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        var ancestor: TreeNode? = root
        while true {
            if (p?.val ?? 0) < (ancestor?.val ?? 0) && (q?.val ?? 0) < (ancestor?.val ?? 0) {
                ancestor = ancestor?.left
            }
            else if (p?.val ?? 0) > (ancestor?.val ?? 0) && (q?.val ?? 0) > (ancestor?.val ?? 0) {
                ancestor = ancestor?.right
            }
            else {
                break
            }
        }
        return ancestor
    }
}

复杂度剖析

  • 时刻复杂度：O(n)O(n)，其间 nn 是给定的二叉查找树中的节点个数。剖析思路与办法一相同。

  • 空间复杂度：O(1)O(1)。