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 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 binary search tree: root = [6,2,8,0,4,7,9,null,null,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 nodes2and4is2, since a node can be a descendant of itself according to the LCA definition.
首先，退出情况起码可以写写。
边界情况。这题比较特殊，要考虑到左边、右边一边就是根节点的情况
从左右的角度思考。也没法思考吧
root.left = 这样没辙。其实就是这么写的，不用怀疑！这一步叫做divide
conquer指的是征服（需要进一步完成具体实现），好吧。其实好像都是这样写的！好吧，更加理解DC了！
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //边界情况。这题比较特殊，要考虑到左边、右边一边就是根节点的情况 if ((root == null) || (p == root) || (q == root)) return root; //分隔 divide TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); //实现 conquer //都不空，左右一个为空，都空 if ((left != null) && (right != null)) { return root; }else if (left != null) { return left; }else if (right != null) { return right; }else { return null; } //return root; } }
235. Lowest Common Ancestor of a Binary Search Tree 235.二叉搜索树的最低共同祖先
原文：https://www.cnblogs.com/immiao0319/p/12961197.html
