# 问题 原题链接：[https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/) Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” ``` _______6______ / \ __2__ __8__ / \ / \ 0 _4_ 7 9 / \ 3 5 ``` Example 1: ``` Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6. ``` Example 2: ``` Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition. ``` Note: - All of the nodes' values will be unique. - p and q are different and both values will exist in the BST. # 分析过程 - 输入：一棵二叉搜索树和两个节点，a 和 b - 输出：这两个节点的最小公共节点 - 思路：遍历树，如果 a 和 b 都比当前节点小，那么肯定在左子树；都比当前大，那么肯定在右子树；如果 a 和 b 一个比当前节点大，一个比当前节点小，那么当前节点就是最小公共节点。如果 a 和 b 其中有一个和当前相等，那么这个点就是最小公共节点。 # 解决方法 ```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; } // 当前节点在 a 和 b 之间的时候 if (((root->val > p->val) && (root->val < q->val)) || ((root->val > q->val && root->val < p->val))) { return root; } // 当前节点比 a 和 b 都大的时候 if ((root->val > p->val) && (root->val > q->val)) { return lowestCommonAncestor(root->left, p, q); } // 当前节点比 a he b 都小的时候 if ((root->val < p->val) && (root->val < q->val)) { return lowestCommonAncestor(root->right, p, q); } // 理论上不会走到这里 assert(0); } }; ``` 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[6] root.left = nodes[2] nodes[2].left = nodes[0] nodes[2].right = nodes[4] nodes[4].left = nodes[3] nodes[4].right = nodes[5] root.right = nodes[8] nodes[8].left = nodes[7] nodes[8].right = nodes[9] func lowestCommonAncestor(_ root: TreeNode?, a: Int, b: Int) -> TreeNode? { // 到底了 guard let root = root else { return nil } // 当前节点和 a 或者 b 相等的时候 if root === a || root === b { return root } // 当前节点在 a 和 b 之间的时候 if (root.val > a.val && root.val < b.val) || (root.val > b.val && root.val < a.val) { return root } // 当前节点比 a 和 b 都大的时候 if root.val > a.val && root.val > b.val { return lowestCommonAncestor(root.left, a: a, b: b) } // 当前节点比 a he b 都小的时候 if root.val < a.val && root.val < b.val { return lowestCommonAncestor(root.right, a: a, b: b) } // 理论上不会走到这里，可以选择断言或者 fatalError return nil } print(lowestCommonAncestor(root, a: 2, b: 4)?.val ?? "nil") print(lowestCommonAncestor(root, a: 5, b: 8)?.val ?? "nil") ```