# 问题 原题链接：[https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/) Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4] ``` _______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4 ``` Example 1: ``` Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of of nodes 5 and 1 is 3. ``` Example 2: ``` Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. ``` # 分析过程 - 输入：一棵二叉树和两个节点 p、q - 输出：最小公共节点 - 思路：遍历树，看左右子树能否找到 p 和 q。如果当前节点不是 p 也不是 q，有三种情况：1、p 和 q 都位于左子树，那么遍历左子树时候会返回 p 或 q，而右子树会返回空。2、p 和 q 都在右子树，同上。3、p 和 q 分别在左子树和右子树，则当前节点就是最小公共节点。 # 解决方法 ```cpp class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 到底了 if (!root) { return nullptr; } // 如果是 a 和 b 的其中一个，直接返回当前节点 if (root == p || root == q) { return root; } TreeNode *left = lowestCommonAncestor(root->left, p, q); TreeNode *right = lowestCommonAncestor(root->right, p, q); if (left != nullptr && right != nullptr) { // 如果左右都不是空，则说明 a 和 b 分别在左右子树 return root; } else { // 其中有一个不是空，另一个是空，则说明 a 和 b 都在不为空的那一边 return (left != nullptr) ? left : right; } } }; ``` Swift 解法（此题在 LeetCode 中不支持该语言）： ```swift class TreeNode { var val: Int var left: TreeNode? var right: TreeNode? init(_ val: Int) { self.val = val self.left = nil self.right = nil } } // 构造和题目中一致的树 var nodes = Array<TreeNode>.init() for i in 0...9 { nodes.append(TreeNode.init(i)) } let root = nodes[3] root.left = nodes[5] nodes[5].left = nodes[6] nodes[5].right = nodes[2] nodes[2].left = nodes[7] nodes[2].right = nodes[4] root.right = nodes[1] nodes[1].left = nodes[0] nodes[1].right = nodes[8] func lowestCommonAncestor(_ root: TreeNode?, a: TreeNode, b: TreeNode) -> TreeNode? { // 到底了 guard let root = root else { return nil } // 如果是 a 和 b 的其中一个，直接返回当前节点 if root === a || root === b { return root } let left = lowestCommonAncestor(root.left, a: a, b: b) let right = lowestCommonAncestor(root.right, a: a, b: b) // 如果左右都不是空，则说明 a 和 b 分别在左右子树 if left != nil && right != nil { return root } else { // 其中有一个不是空，另一个是空，则说明 a 和 b 都在不为空的那一边 return (left != nil) ? left : right } } print(lowestCommonAncestor(root, a: nodes[2], b: nodes[4])?.val ?? "nil") print(lowestCommonAncestor(root, a: nodes[5], b: nodes[8])?.val ?? "nil") ```