IOS 算法(基础篇) ----- 二叉搜索树的最近公共祖先

又是一道树的问题
题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

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

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

         6
     /       \
   2          8
  /  \       /  \
 0    4     7    9
     /  \
    3    5

给定 p = 2, q = 8

返回: 6

给定 p = 2, q = 4

返回: 2

解题思路

首先我们了解下二叉搜索树特点, 左子树都比根节点小, 而右子树都比根节点大
我们可以根据这个特性, 处理这个问题

1.迭代查找

这种方法比较好理解
如果 p, q值 都小于 根结点，那么我们去左子树寻找
如果 p, q值 都大于 根结点，那么我们去右子树寻找
其他情况，即 p, q值分别在当前根结点的左右，于是 当前根结点就是最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

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

2.递归查找

利用二叉搜索树的特性，在root的左右子树定向寻找最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

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

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址