Leetcode 235. 二叉搜索树的最近公共祖先 C++
文章图片
思路 因为是二叉搜索树，可以充分利用二叉搜索树的性质来做这道题。二叉搜索树左子树的节点值一定全部小于根节点，右子树的节点值全部大于根节点。所以：
（1）如果所找的两个节点一个大于根节点的值，一个小于根节点的值，那么这个根节点就为最近的祖先。
（2）若是同时小于根节点，那么就去左子树中找。
（3）如果同时大于根节点，就去右子树中找答案。
【Leetcode 235. 二叉搜索树的最近公共祖先 C++】最近自己编写递归程序的能力有下滑，带返回值递归的处理居然都不会了。递归的时候，一样用return就好
解答
/**
* Definition for a binary tree node.
* struct TreeNode {
*int val;
*TreeNode *left;
*TreeNode *right;
*TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return root;
if( (root->val >= p->val && root->val <= q->val) || (root->val <= p->val && root->val >= q->val)) return root;
else if(root->val >p->val && root->val >q->val) return lowestCommonAncestor(root->left, p, q);
else if(root->val val && root->val val) return lowestCommonAncestor(root->right, p, q);
else return NULL;
}
};
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 数据结构和算法|LeetCode 的正确使用方式