给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
LeetCode：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
image.png
/**
* 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
* }
* }
*/
class Solution {
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
// 到底了
guard let root = root else { return nil }
// 前序位置：遇到目标值就可以返回了，不必再向下
if root === p || root === q {
return root
}
let left = lowestCommonAncestor(root.left, p, q)
let right = lowestCommonAncestor(root.right, p, q)
// 后序位置：已经知道了左右子树是否有目标节点
// 如果该节点左右子树都有目标值，说明该节点是最近公共祖先
if left != nil, right != nil {
return root
}
// 只有左子树或右子树有目标节点
return left ?? right
}
}
image.png
