235. 二叉搜索树的最近公共祖先
思路:
因为是二叉搜索树,所以公共祖先一定是位于这两个节点区间中的
问题:
为什么第一个是这两个中间的例子,就是公共祖先呢?因为是最先符合要求的,
代码:
1 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 2 { 3 if (!root) return NULL; 4 if (root == p || root == q) return root; 5 6 TreeNode* left = NULL, * right = NULL; 7 if (root->left) left = lowestCommonAncestor(root->left, p, q); 8 if (root->right) right = lowestCommonAncestor(root->right, p, q); 9 10 if (left && right) return root; 11 else if (!left && right) return right; 12 else if (!right && left) return left; 13 else return NULL; 14 }