swift算法（二叉搜索树的最近公共祖先）算法

1、描述
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树T的两个结点p、q，最近公共祖先表示为一个结点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）”。
例如，给定如下二叉搜索树：root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]

例1：输入：root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]， p = 2，q = 8
输出：6
解释：节点 2 和节点 8 的最近公共祖先是 6
例1：输入：root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]， p = 2，q = 4
输出：2
解释：节点 2 和节点 4 的最近公共祖先是2，因为根据定义最近公共节点可以为节点本身

2、算法
二叉搜索树BST的性质：
节点N 左子树上的所有节点的值都小于等于节点N 的值
节点N 右子树上的所有节点的值都大于等于节点N 的值
左子树和右子树也都是 BST
1）递归
思想：节点p，q 的最近公共祖先（LCA）是距离这两个节点最近的公共祖先节点。在这里最近考虑的是节点的深度。
算法：
从根节点开始遍历树
如果节点p 和节点q 都在右子树上，那么以右孩子为根节点继续 1 的操作
如果节点p 和节点q 都在左子树上，那么以左孩子为根节点继续 1 的操作
如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节p 和节点q 的 LCA 了
时间复杂度：O(n)

func lowestCommonAncestor(_ root : TreeNode?, _ p : TreeNode?, _ q : TreeNode?)->TreeNode?{ /*递归 O(n)*/ let parentVal : Int = (root?.val)! let pVal : Int = (p?.val)! let qVal : Int = (q?.val)!if pVal > parentVal && qVal > parentVal { return lowestCommonAncestor(root?.right, p, q) }else if pVal < parentVal && qVal < parentVal{ return lowestCommonAncestor(root?.left, p, q) }else{ return root } }

2）迭代
思想：与递归类似，不同之处在于是用迭代的方法替代了递归来遍历整棵树
时间复杂度：O(n)

func lowestCommonAncestor(_ root : TreeNode?, _ p : TreeNode?, _ q : TreeNode?)->TreeNode?{ /* 迭代 */ let pVal : Int = (p?.val)! let qVal : Int = (q?.val)!var node = rootwhile node != nil { let parentVal : Int = (node?.val)! //如果节点p 和节点q 都在右子树上，那么以右孩子为根节点继续操作 if pVal > parentVal && qVal > parentVal { return lowestCommonAncestor(root?.right, p, q) }else if pVal < parentVal && qVal < parentVal{ //如果节点p 和节点q 都在左子树上，那么以左孩子为根节点继续操作 return lowestCommonAncestor(root?.left, p, q) }else{ return node } } return nil }

【swift算法（二叉搜索树的最近公共祖先）】