系列文章目录
刷题笔记（一）–数组类型：二分法
刷题笔记（二）–数组类型：双指针法
刷题笔记（三）–数组类型：滑动窗口
刷题笔记（四）–数组类型：模拟
刷题笔记（五）–链表类型：基础题目以及操作
刷题笔记（六）–哈希表：基础题目和思想
刷题笔记（七）–字符串：经典题目
刷题笔记（八）–双指针：两数之和以及延伸
刷题笔记（九）–字符串：KMP算法
刷题笔记（十）–栈和队列：基础题目
刷题笔记（十一）–栈和队列：Top-K问题
刷题笔记（十二）–复习：排序算法
刷题笔记（十三）–二叉树：前中后序遍历（复习）
刷题笔记（十四）–二叉树：层序遍历和DFS,BFS
刷题笔记（十五）–二叉树：属性相关题目
刷题笔记（十六）–二叉树：修改与构造
刷题笔记（十七）–二叉搜索树：关于属性问题
前言
二叉树快完了，加油！！！
题录
236. 二叉树的最近公共祖先
题目链接如下：
题目截图如下：
这道题怎么做呢？其实是要分步骤进行
步骤一
给出根节点，和目标节点，然后查看目标节点是否为根节点的子树。这个很简单不是？
public boolean find(TreeNode root,TreeNode target){
if(root == null) return false;
if(root == target) return true;
return find(root.left,target) || find(root.right,target);
}
步骤二
那接下来肯定就是要分情况讨论了
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//接下来就是进行判断
if(root == null) return null;
if(root == p || root == q) return root;//如果说p或者q任意一个为根节点，那祖先肯定是根节点
//如果说p q节点都在左侧，那就去左子树找祖先
if(find(root.left,p) && find(root.left,q)) return lowestCommonAncestor(root.left,p,q);
//如果说p q节点都在右侧，那就去右子树找祖先
if(find(root.right,p) && find(root.right,q)) return lowestCommonAncestor(root.right,p,q);
//如果不同时在一侧，那当前节点肯定就是祖先
return root;
}
步骤三
第三步是什么呢？肯定就是化简啦，上面那样写肯定是可以的，但是有点长。先上代码吧，然后再对代码讲解一下
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;//这一步是关键
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left == null && right == null) return null;
if(left == null) return right;
if(right == null) return left;
return root;
}
这个代码就是把步骤一和步骤合并，但是这里吧…emmm，重点就是：后序遍历。和上面一样，分成两步来看
步骤一：
这是第一步，就是一个不断递归的过程，然后去寻找p和q节点。
这是第二步，是对寻找的情况进行判断。
这两步就是对每一层递归的分解，好像有点乱是不是？？emmm，先停一下，后续如果我可以组织好自己的语言再继续。
235. 二叉搜索树的最近公共祖先
题目链接：
题目截图：
其实是可以当做一个普通的树来进行处理的，但是这里既然提到了二叉搜索树，和上题一样，甚至代码都不用变动。
但是呢，这里既然提到了二叉搜索树，那么肯定是可以通过二叉搜索树的性质对当前时间复杂度进行优化。
public class 二叉搜索树的公共祖先 {
//二叉树的公共祖先是后序遍历了，那这里我还可以后续遍历嘛？我第一思路是前序遍历
//前序遍历还是有点小问题，return root重复了
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left,p,q);
}
if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right,p,q);
}
return root;
}
}