- 前言
- 1. 常规算法
- 1.1 递归遍历
- 1.2 迭代遍历
- 1.3 层次遍历
- 二叉树
- 226. 翻转二叉树（简单）
- 101. 对称二叉树（简单）
- 100. 相同的树（简单）
- 572. 另一棵树的子树（简单）
- 剑指 Offer 26. 树的子结构（中等）
- 104. 二叉树的最大深度（简单）
- 111. 二叉树的最小深度（简单）
- 222. 完全二叉树的节点个数（中等）*
- 110. 平衡二叉树（简单）*
- 257. 二叉树的所有路径（简单）*
- 404. 左叶子之和（简单）
- 513. 找树左下角的值（中等）
- 112. 路径总和（简单）
- 113. 路径总和 II（中等）
- 105. 从前序与中序遍历序列构造二叉树（中等）
- 106. 从中序与后序遍历序列构造二叉树（中等）
- 654. 最大二叉树（中等）
- 617. 合并二叉树（简单）
- 二叉搜索树
- 700. 二叉搜索树中的搜索（简单）
- 98. 验证二叉搜索树（中等）
- 530. 二叉搜索树的最小绝对差（简单）
- 501. 二叉搜索树中的众数（简单）*
- 236. 二叉树的最近公共祖先（中等）
- 235. 二叉搜索树的最近公共祖先（简单）
- 701. 二叉搜索树中的插入操作（中等）
- 450. 删除二叉搜索树中的节点（中等）*
- 669. 修剪二叉搜索树（中等）
- 108. 将有序数组转换为二叉搜索树（简单）*
- 538. 把二叉搜索树转换为累加树（中等）
关于以下代码的补充可看如下链接：
代码随想录中的二叉树理论以及代码
本文主要根据该链接的学习路线进行学习，通过阅览其思路以及自我的认知，加上了代码注释
方便自我的学习，感兴趣的同学也可收藏关注
二叉树专栏这一块 部分代码没有用代码回想录的，主要是代码顺序以及有些思路或者图解引用了
1. 常规算法遍历中使用递归或者迭代是很常见的，尤其是前序中序后序
1.1 递归遍历前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val); //
inorder(root.right, list);
}
}
后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
public List postorderTraversal(TreeNode root) {
List res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val); //
}
}
1.2 迭代遍历
此处的迭代遍历没有使用代码随想录的代码，如果感兴趣可百度搜索就有，它的统一迭代遍历也可
//前序遍历
class Solution {
public List preorderTraversal(TreeNode root) {
List list = new ArrayList<>();
if (root == null) {
return list;
}
LinkedList stack = new LinkedList<>();
TreeNode node = root;
while (node != null||!stack.isEmpty() ) {
while (node != null) {
list.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return list;
}
}
中序遍历
class Solution {
public List inorderTraversal(TreeNode root) {
List list = new ArrayList<>();
LinkedList stk = new LinkedList<>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
list.add(root.val);
root = root.right;
}
return list;
}
}
后序遍历
class Solution {
public List postorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null)return list;
LinkedList stk=new LinkedList<>();
//创建一个空指针，主要为了记忆 根节点，往回退
TreeNode prev=null;
while(root!=null||!stk.isEmpty()){
while(root!=null){
stk.push(root);
root=root.left;
}
//出栈之后遍历右节点
root=stk.pop();
//如果右边无数据，则将该节点加入到list列表中。并且将其root置为空，主要是为了将其出栈，往上退一个格子
if(root.right==null||root.right==prev){
list.add(root.val);
//往上退的格子标记为prev
prev=root;
root=null;
}else{
//如果右边有数据，则继续进栈
stk.push(root);
root=root.right;
}
}
return list;
}
}
1.3 层次遍历
自上而下开始层次遍历：
class Solution {
public List> levelOrder(TreeNode root) {
List> list=new ArrayList>();
if(root==null) return list;
Queue que=new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
Listsonlist=new LinkedList<>();
int n=que.size();
for(int i=0;i
自下而上开始层次遍历：修改最后的代码格式为list.add(0,sonlist);
输出二叉树的右视图：则每个size中输出最后一个节点即可
leetcode：199. 二叉树的右视图
输出每一个层次遍历的平均数
leetcode：637. 二叉树的层平均值
N叉树的层次遍历，注意其中的区别：
leetcode：429. N 叉树的层序遍历
leetcode：515. 在每个树行中找最大值
下面这个返回的节点不是list，为做以区分，此处放出完整代码以及注释
leetcode：116. 填充每个节点的下一个右侧节点指针
class Solution {
public Node connect(Node root) {
//不用这个，类型不对
//List list=new ArrayList<>();
if(root==null)return root;
LinkedList que=new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int n=que.size();
for(int i=0;i
上面的思路，这道题同样可以套用
leetcode：117. 填充每个节点的下一个右侧节点指针 II
二叉树
226. 翻转二叉树（简单）
leetcode：226. 翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)return null;
//放在一个节点中记录值，为了递归后面root的指向
TreeNode l=invertTree(root.left);
TreeNode r=invertTree(root.right);
root.left=r;
root.right=l;
return root;
}
}
或者在节点中直接反转：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
甚至是使用层次遍历，在每一层的节点中进行翻转
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
LinkedList que=new LinkedList<>();
que.offer(root);
//层次遍历每一层都进行反转左右节点
while(!que.isEmpty()){
TreeNode node= que.poll();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if(node.left!=null)que.offer(node.left);
if(node.right!=null)que.offer(node.right);
}
return root;
}
}
错误写法：
101. 对称二叉树（简单）
leetcode：101. 对称二叉树
递归做法：
class Solution {
public boolean isSymmetric(TreeNode root) {
return ss(root,root);
}
public boolean ss(TreeNode L1,TreeNode L2){
if(L1==null&&L2==null) return true;
if(L1 ==null ||L2==null) return false;
//每一次递归的条件都是数值相等，而且L1左指针等同于L2右指针，并且L1右指针等同于L2左指针
return L1.val==L2.val && ss(L1.left,L2.right) && ss(L1.right,L2.left);
}
}
广度优先遍历：
class Solution {
public boolean isSymmetric(TreeNode root) {
return ss(root,root);
}
//返回的类型为boolean
public boolean ss(TreeNode L1,TreeNode L2){
LinkedList que=new LinkedList<>();
//层次遍历，root节点都添加一遍
que.offer(L1);
que.offer(L2);
while(!que.isEmpty()){
//输出的时候返回给u与v
TreeNode u= que.poll();
TreeNode v = que.poll();
//如果两个都为null则继续
if(u==null&&v==null)continue;
//这三个条件有哪个条件不满足则返回为false
if(u==null||v==null||u.val!=v.val)return false;
//入队列的时候 看清楚顺序
que.offer(u.left);
que.offer(v.right);
que.offer(u.right);
que.offer(v.left);
}
return true;
}
}
100. 相同的树（简单）
题目：leetcode：100. 相同的树
思路：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null)return true;
if(p==null ||q==null)return false;
return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
广度优先遍历，和上一道题差不多，此处就不写了
572. 另一棵树的子树（简单）
题目：leetcode：572. 另一棵树的子树
主要是注意限制的范围：
思路：
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//节点个数是从1开始 。所以此处没有空树这个说法
//这个主要为了后续递归的调用
if(subRoot==null)return true;
if(root==null)return false;
return (istree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot));
}
public boolean istree(TreeNode root,TreeNode subRoot){
//这个一定要加上，条件比较完善，因为前面不是那样判断的，所以这个要加上
//对称美，如果不加上，和下面的题目一样代码 就会出现这个样例过不了
//输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
//输出：false
if(root ==null && subRoot==null)return true;
if(root==null || subRoot== null)return false;
return (root.val==subRoot.val) &&istree(root.left,subRoot.left)&& istree(root.right,subRoot.right);
}
}
剑指 Offer 26. 树的子结构（中等）
题目：leetcode：剑指 Offer 26. 树的子结构
主要的限制条件为：0 <= 节点个数 <= 10000
（(约定空树不是任意一个树的子结构)）
思路：
所以一开始为空的时候都为false，空树不是它的子树
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
//if(B==null)return true;
//if(A==null) return false
//特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false
//也就是默认都不为空的时候，才会为true
//以下三个递归自身，左节点，右节点
return (A!=null && B!=null) && (dfs(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));
}
public boolean dfs(TreeNode A,TreeNode B){
//当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true
if(B==null)return true;
//如果A为null以及B不为null的时候，则说明还有节点没判断完
if(A==null)return false;
return (A.val==B.val) && dfs(A.left,B.left)&&dfs(A.right,B.right);
}
}
104. 二叉树的最大深度（简单）
leetcode：104. 二叉树的最大深度
这道题同样也可使用dfs进行递归调用
111. 二叉树的最小深度（简单）
求最大深度以及最小深度也可使用层次遍历（看清楚深度的第一层初始化定义是什么）
最小深度遍历：
这道题比最大深度多了一个判断条件，都为null及时返回
leetcode：111. 二叉树的最小深度
关于最小深度的遍历可看如下题解（题解来源于xcoder-4）
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 计算左子树的深度
int left = minDepth(root.left);
// 计算右子树的深度
int right = minDepth(root.right);
// 如果左子树或右子树的深度不为 0，即存在一个子树，那么当前子树的最小深度就是该子树的深度+1。也就是某一个为0，要么left+1，要么right+1
// 如果左子树和右子树的深度都不为 0，即左右子树都存在，那么当前子树的最小深度就是它们较小值+1
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
}
或者是这种写法：（题解来源于宏桑）
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
else if (root.left == null) return minDepth(root.right) + 1;
else if (root.right == null) return minDepth(root.left) + 1;
else return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
222. 完全二叉树的节点个数（中等）*
统计节点个数
leetcode：222. 完全二叉树的节点个数
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}else {
int a=countNodes(root.left);
int b=countNodes(root.right);
return a+b+1;
}
}
}
广度优先遍历：
110. 平衡二叉树（简单）*
题目链接：
leetcode：110. 平衡二叉树
自底向上的递归，有点类似后序遍历
class Solution {
public boolean isBalanced(TreeNode root) {
//返回的高度一定是非负整数，如果abs一直大于1，则会有负数的
return heigh(root)>=0;
}
public int heigh(TreeNode root){
if(root==null)return 0;
//从上往下递归遍历，一开始在最下面的一层次遍历
int left=heigh(root.left);
int right=heigh(root.right);
如果左子树或者右子树为-1.则往上层递归直接变为-1。还有一个abs直接大于1
if(left==-1||right==-1||Math.abs(left-right)>1)return -1;
//往上返回的左右子树最大的一个，直接加1。递归条件
return Math.max(left,right)+1;
}
}
或者使用自上而下的递归：
（代码比较难以思考）
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
//一直递归左右子树，往下递归，取其最大然后加1即可
return Math.max(height(root.left), height(root.right)) + 1;
}
}
}
257. 二叉树的所有路径（简单）*
题目：leetcode：257. 二叉树的所有路径
思路：
class Solution {
List list=new ArrayList<>();
public List binaryTreePaths(TreeNode root) {
//通过String类型传播
backtrace(root,"");
return list;
}
public void backtrace(TreeNode root,String sonpath){
//叶子节点则往回溯
if(root==null)return;
//在上一个路径中的StingBuilder
StringBuilder path=new StringBuilder(sonpath);
path.append(Integer.toString(root.val));
//判断是否为叶子节点，如果是叶子节点，则加入到list中，而且列表添加StringBuilder要转为toString类型
if(root.left==null && root.right==null)list.add(path.toString());
else{
//否则追加这个符号并且回溯
path.append("->");
backtrace(root.left,path.toString());
backtrace(root.right,path.toString());
}
}
}
关于这部分的详细题解可看如下：
ACM 选手图解 LeetCode 二叉树的所有路径（递归 + 非递归）
或者使用更加精简的代码：
class Solution {
public void traversal(TreeNode cur, String path, List result) {
path += cur.val; // 中
if (cur.left == null && cur.right == null) {
result.add(path);
return;
}
if (cur.left!=null) traversal(cur.left, path + "->", result); // 左 回溯就隐藏在这里
if (cur.right!=null) traversal(cur.right, path + "->", result); // 右 回溯就隐藏在这里
}
public List binaryTreePaths(TreeNode root) {
List result = new LinkedList<>();
if (root == null) return result;
traversal(root, "", result);
return result;
}
}
404. 左叶子之和（简单）
题目：leetocde：404. 左叶子之和
思路：
层次遍历的逻辑梳理
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null)return 0;
Queueque=new LinkedList<>();
int sum=0;
que.offer(root);
while(!que.isEmpty()){
int n=que.size();
for(int i=0;i
513. 找树左下角的值（中等）
题目：leetcode：513. 找树左下角的值
思路：
class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root==null)return 0;
Queue que=new LinkedList<>();
//记录最后一个节点的值，因为是层次遍历，所以最后一层的节点的第一个，一定会覆盖前面的值
int res=0;
que.offer(root);
while(!que.isEmpty()){
int n=que.size();
for(int i=0;i
112. 路径总和（简单）
题目：leetcode：112. 路径总和
大致意思如下：判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
思路：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
//递归到下面，发现root为null则返回false
if(root==null)return false;
//每一层都要先减个root的值
targetSum-=root.val;
//提前判断是否下一层左右为空，而且其值也为0，返回true
if(root.left==null && root.right==null && targetSum==0)return true;
//因为是左右子树，所以要返回左右子树的选择
if(root.left!=null){
if(hasPathSum(root.left,targetSum))return true;
}
if(root.right!=null){
if(hasPathSum(root.right,targetSum))return true;
}
//如果都没有执行，返回false
return false;
}
}
或者另外一种写法：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
//递归到下面，发现root为null则返回false
if(root==null)return false;
//提前判断是否下一层左右为空，当前节点是否等于目标值（这是还未减去）
if(root.left==null && root.right==null )return root.val==targetSum;
//因为是左右子树，所以要返回左右子树的选择，而且每个值都要减去其值
if(root.left!=null){
if(hasPathSum(root.left,targetSum-root.val))return true;
}
if(root.right!=null){
if(hasPathSum(root.right,targetSum-root.val))return true;
}
//如果都没有执行，返回false
return false;
}
}
也可简化上面的代码逻辑：
class solution {
public boolean haspathsum(Treenode root, int targetsum) {
if (root == null) return false; // 为空退出
// 叶子节点判断是否符合
if (root.left == null && root.right == null) return root.val == targetsum;
// 求两侧分支的路径和
return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
}
}
广度优先遍历：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
//提前为空返回false
if (root == null) {
return false;
}
//创建两个队列或者两个栈都可。一个用来存储节点，一个用来存储总和
Queue queNode = new LinkedList();
Queue queVal = new LinkedList();
queNode.offer(root);
queVal.offer(root.val);
while (!queNode.isEmpty()) {
TreeNode now = queNode.poll();
int temp = queVal.poll();
//处理根节点，如果下一个左右节点都为null 而且值已经提前相等，则返回true
if (now.left == null && now.right == null && temp==targetSum)return true;
if (now.left != null) {
queNode.offer(now.left);
queVal.offer(now.left.val + temp);
}
if (now.right != null) {
queNode.offer(now.right);
queVal.offer(now.right.val + temp);
}
}
return false;
}
}
113. 路径总和 II（中等）
题目：leetcode：113. 路径总和 II
这道题跟上一题区别在于，大致区别如下：
思路：
回溯递归的思路：
class Solution {
List> list=new ArrayList>();
LinkedList sonlist=new LinkedList<>();
public List> pathSum(TreeNode root, int targetSum) {
if(root==null)return list;
backtrace(root,targetSum);
return list;
}
public void backtrace(TreeNode root,int target){
//边界值超出的话要返回，通过root为null，返回上一层
if(root==null)return;
//不管有没有，先加入节点，后续在判断
sonlist.addLast(root.val);
//每个节点加入之后要减去
target-=root.val;
//判断条件不只是为0，因为到叶子节点，还需要左右节点都为null，才可添加
if(target==0 && root.left==null && root.right==null){
list.add(new ArrayList<>(sonlist));
}
//标准的回溯，没有到叶子节点，则一直左右节点的跑
backtrace(root.left,target);
backtrace(root.right,target);
//如果执行到这都没有，则把叶子节点删除
sonlist.removeLast();
//并且把刚那个节点加回去
target+=root.val;
}
}
105. 从前序与中序遍历序列构造二叉树（中等）
题目：leetcode：105. 从前序与中序遍历序列构造二叉树
思路：
递归调用，区分左右子树，以及它的代码逻辑
（用时3ms）
//先序遍历和中序遍历
//通过找到先序遍历的第一个根节点（按照顺序一个个加），这个功能可以放在递归的逻辑上
//根据找到的根节点的值，去遍历中序遍历，找到与根节点的值一样的下标
//左子树的长度：下标减去中序遍历刚开始的点，就是全部左子树的数量。右子树的长度：下标加1到结尾的长度
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//通过两个子树 也就是两个数组的范围进行递归调用
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int []preorder,int p_start,int p_end,int [] inorder,int i_start,int i_end){
//因为一开始的初始值条件是【0，n-1】，所以只要超出了边界就返回null
if(p_start>p_end)return null;
//通过前序遍历的第一个节点，找到其数值，并且新建子树的一个点
int root_val=preorder[p_start];
TreeNode root=new TreeNode(root_val);
//创建一个根节点的index值（这个index对应中序遍历的根）
int index=0;
for(int i=i_start;i<=i_end;i++){
if(root_val==inorder[i]){
index=i;
break;
}
}
//输出左子树的长度，主要为了后续左右子树的递归调用
int left=index-i_start;
//左子树以及右子树的递归调用，通过其长度
//（先序左子树，起点+1，起点+左子树长度）（中序左子树，起点，根节点-1）
root.left=build(preorder,p_start+1,p_start+left,inorder,i_start,index-1);
//（先序右子树，起点+左子树长度+1）（中序右子树，根节点+1，结尾节点）
root.right=build(preorder,p_start+left+1,p_end,inorder,index+1,i_end);
return root;
}
}
为了进一步的优化：
用hashmap存储中序遍历的各个节点值（主要为了配对先序每一个一开始的根节点的位置）
（用时1ms）
关于以上代码进一步的优化，可看此题解：
详细通俗的思路分析，多解法
106. 从中序与后序遍历序列构造二叉树（中等）
题目：leetcode：106. 从中序与后序遍历序列构造二叉树
思路：
大体的思路和上一题很相像
此处给出部分细节即可
这幅图来源于
图解构造二叉树之中序+后序
class Solution {
Mapmap=new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i=0;i
654. 最大二叉树（中等）
题目：leetcode：654. 最大二叉树
此处是用不了二分查找（二分查找为有序，也可部分有序使用，此处无序）
class Solution {
//List list=new ArrayList<>();
public TreeNode constructMaximumBinaryTree(int[] nums) {
return ss(nums,0,nums.length-1);
}
public TreeNode ss(int []nums,int left,int right){
if(left>right)return null;
//找最大的节点的下标值，一开始给予的最大下标为最左边
int maxid=left;
for(int i=left;i<=right;i++){
//一个个判断其值跟每个下标的比较值，然后覆盖最大下标的值，（下标值是从小到大遍历，不会混乱，下一个i也会+1）
if(nums[i]>nums[maxid])maxid=i;
}
//每个节点最大值都new一遍
TreeNode root =new TreeNode(nums[maxid]);
// 错误用法，不是找中间节点，是找最大节点。类似快排思路
// int mid=left+(right-left)/2;
//list.add(nums[mid]);
//遍历左右节点
root.left=ss(nums,left,maxid-1);
root.right=ss(nums,maxid+1,right);
return root;
}
}
617. 合并二叉树（简单）
题目：leetcode：617. 合并二叉树
大致意思是合并两个二叉树
思路：
以下为先序遍历，也可改变一些节点，将其变为中序或者后序
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null)return root2;
if(root2==null)return root1;
root1.val=root1.val+root2.val;
root1.left=mergeTrees(root1.left,root2.left);
root1.right= mergeTrees(root1.right,root2.right);
return root1;
}
}
如果不改变节点信息，则创建一个临时二叉树也可
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null)return root2;
if(root2==null)return root1;
//创建临时二叉树，具体变化在这里
TreeNode root=new TreeNode(0);
root.val=root1.val+root2.val;
root.left=mergeTrees(root1.left,root2.left);
root.right= mergeTrees(root1.right,root2.right);
return root;
}
}
层次遍历同理，此处展示代码
class Solution {
// 使用队列迭代
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 ==null) return root1;
Queue queue = new LinkedList<>();
queue.offer(root1);
queue.offer(root2);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
// 此时两个节点一定不为空，val相加
node1.val = node1.val + node2.val;
// 如果两棵树左节点都不为空，加入队列
if (node1.left != null && node2.left != null) {
queue.offer(node1.left);
queue.offer(node2.left);
}
// 如果两棵树右节点都不为空，加入队列
if (node1.right != null && node2.right != null) {
queue.offer(node1.right);
queue.offer(node2.right);
}
// 若node1的左节点为空，直接赋值
if (node1.left == null && node2.left != null) {
node1.left = node2.left;
}
// 若node2的左节点为空，直接赋值
if (node1.right == null && node2.right != null) {
node1.right = node2.right;
}
}
return root1;
}
}
二叉搜索树
性质：
- 左子树所有节点的元素值均小于根的元素值；
- 右子树所有节点的元素值均大于根的元素值。
如果要搜索一条边，递归函数就要加返回值，因为有目标节点，需要return返回
不加return 就是遍历整个树
讲解二叉搜索树的同时，先回复一下二叉树的递归以及迭代（先中后以及层次遍历）
此处讲解一下递归
class Solution {
// 递归，普通二叉树
public TreeNode searchBST(TreeNode root, int val) {
//如果左节点问null或者相等直接返回root
if (root == null || root.val == val) {
return root;
}
//递归左节点
TreeNode left = searchBST(root.left, val);
//左节点不为空，则返回左节点
if (left != null) {
return left;
}
return searchBST(root.right, val);
}
}
700. 二叉搜索树中的搜索（简单）
题目：leetcode：700. 二叉搜索树中的搜索
大致意思如下：
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
思路：
递归
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
//下面这两种情况可以合并在一起，直接返回root即可
// if(root==null)return null;
// if(root.val==val)return root;
if(root==null || root.val==val)return root;
if(root.val>val)return searchBST(root.left,val);
else if(root.val
直接通过迭代的方式进行：
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root!=null){
if(root.val==val){
return root;
}
if(root.val>val)root=root.left;
else if (root.val
98. 验证二叉搜索树（中等）
题目：leetode：98. 验证二叉搜索树
思路：
测试数据中有int最小值，所以定义为longlong的类型，初始化为longlong最小值。
记忆一个最小的节点，通过对比比较
class Solution {
//本身测试数据有比int数据要小，所以定义为long 类型
long pre=Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
//从下往上递归，为null的时候都为true
if(root==null)return true;
//左节点递归
boolean left=isValidBST(root.left);
//根节点处理，如果是按照顺序，则记住pre是上一个节点，遍历到最后是顺序的，就是二叉搜索树
//使用pre来记住上一个节点
if(root.val>pre)pre=root.val;
//如果不是，则提前返回false，不用再搜索右子树了
else return false;
boolean right=isValidBST(root.right);
return left&&right;
}
}
兴许有更小的节点，所以直接定义为null
具体如下：
530. 二叉搜索树的最小绝对差（简单）
题目：leetcode：530. 二叉搜索树的最小绝对差
思路：
递归的思路：
class Solution {
//因为数据中的节点最小值是0以上，所以初始化的最小值节点需要负数任意一个
int pre=-1;
//遍历最小值的那个节点
int ans=Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root==null)return 0;
min(root);
return ans;
}
public void min(TreeNode root){
//采用中序遍历，遍历到叶子节点，即往回塑
if(root==null)return ;
min(root.left);
//处理根节点，刚开始递归到最后 处理的 第一个节点，将其节点的值赋值给pre
//如果不这样处理，pre的值就一直都是最小值
if(pre==-1){
pre=root.val;
}else {
ans=Math.min(ans,root.val-pre);
pre=root.val;
}
min(root.right);
}
}
为了避免这种情况的发生，直接不定义最小节点：
总体思路：
定义一个pre保存上一个节点
在递归到处理第一个根节点的时候 pre不为null也很巧妙的可以保存root节点的值
而且因为要找到绝对值的点，二叉搜索树都是前一个节点减去后一个保存的节点（中序遍历）
501. 二叉搜索树中的众数（简单）*
题目：leetcode：501. 二叉搜索树中的众数
大致意思是：如果树中有不止一个众数，可以按 任意顺序 返回。
思路：
class Solution {
//定义一个列表去加所有大数字，也就是众数比较多的数字
List list=new ArrayList<>();
//统计数字
int maxcount=0;
int count=0;
//保存上一个节点的值
TreeNode pre=null;
public int[] findMode(TreeNode root) {
if(root==null)return new int[0];
find(root);
//将其列表中的节点都转换为数组，之后以数组的形式输出即可
int [] res=new int [list.size()];
for(int i=0;imaxcount){
list.clear();
list.add(root.val);
maxcount=count;
//一开始两者都是0的时候，会添加第一个节点，刚好也满足情况
//这种情况还有一个比较特殊，就是众数都是相等的情况下
}else if(count==maxcount){
list.add(root.val);
}
//保存上一个节点
pre=root;
find(root.right);
}
}
236. 二叉树的最近公共祖先（中等）
题目：leetcode：二叉树的最近公共祖先
思路：
要往上返回其公共节点，从下往上遍历，而且能返回节点值，默认使用后序遍历（本身就有回溯的想法）
其图解可看 【代码回想录】的图解：
通过递归构造的思路：
具体代码如下
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//两个初始条件，要么为null，要么跟p或者q相等
//这是递归刚开始的判断
//判断其左右节点如果为null，则返回上去即为null
if(root==null)return null;
//如果判断的节点本身有一个相等，优先返回为自身。不用再去判断叶子节点
if(root==p||root==q)return root;
//上面的条件如果都不满足，则通过递归，后续遍历，所以先递归左节点，在递归右节点
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
//递归之后的判断，本身叶子节点为null，一开始的初始判断条件已经传回去了
//如果左边传回为null，代表这个值不相等或者为叶子节点。直接返回右节点的值。右节点同理
//如果左右都不想等，则返回的值为自身，也就是在2 7 4 这个子树中，2的左节点为7，右节点为4。则传回2回去即可
if(left==null)return right;
else if (right==null)return left;
else return root;
}
}
235. 二叉搜索树的最近公共祖先（简单）
题目：leetcode：235. 二叉搜索树的最近公共祖先
思路：
这道题同样可以使用上一题的题解
（时间7ms）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null)return null;
if(root==p|root==q)return root;
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left==null)return right;
else if(right==null)return left;
else return root;
}
}
但是这么用有些拉高了复杂度
因为本身就是搜索树
通过判断左右遍历其节点即可
如果相等直接返回root即可
（时间6ms）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val>p.val&&root.val>q.val)return lowestCommonAncestor(root.left,p,q);
else if(root.val
使用这种方式会直接超时
故修改一下逻辑：(时间5ms)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(true){
if(root.val>p.val&&root.val>q.val){
root=root.left;
}
else if(root.val
701. 二叉搜索树中的插入操作（中等）
题目：leetcode：701. 二叉搜索树中的插入操作
思路：
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//如果走到这，发现为空，则创建一个节点的值即可
if(root==null)return new TreeNode(val);
//如果左右节点不同，则通过root中的左右节点重新指向即可，递归创建左右子树
//这道题不能使用return 去返回上一个节点，因为输出的时候是完整的一个树，有指向的树
if(root.val>val)root.left= insertIntoBST(root.left,val);
else if(root.val
使用模拟算法：
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//先判断初始值是否为null，如果为null，直接创建一个节点值
if (root == null) {
return new TreeNode(val);
}
//使用临时节点遍历
TreeNode node=root;
//总条件是node不为null，一直遍历
while(node!=null){
//细化的条件是判断方向
if(node.val>val){
//每一次添加的时候都要判断是否为null，如果为null则直接指向新的节点
if(node.left==null){
node.left=new TreeNode(val);//
break;
}else{
//不为null的话，指向旧节点
node=node.left;
}
//思路同上
}else if(node.val
450. 删除二叉搜索树中的节点（中等）*
题目：leetocde：450. 删除二叉搜索树中的节点
思路：
具体思路如下：
重点知道怎么删除
如果看不懂代码逻辑可看代码随想录的解释：
450.删除二叉搜索树中的节点
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//1. 没找到删除的节点，遍历到空节点直接返回了
if(root==null)return null;
//本身是二叉搜索树
if(root.val>key){
root.left=deleteNode(root.left,key);
}else if(root.val
669. 修剪二叉搜索树（中等）
题目：leetcode：669. 修剪二叉搜索树
（本身就是二叉搜索树了，只需要删除没必要的节点）
大致意思如下：
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
//节点不存在，则直接返回null即可
if(root==null)return null;
//考虑到像删除 二叉搜索树比较麻烦，处理数据比较多，所以考虑反方面。直接将不满足的指向另外一边即可
if(root.valhigh){
//如果不在这个范围，则裁剪右节点，返回其左节点上去
return trimBST(root.left,low,high);
}
//遍历满足条件的节点，将其左节点指向左节点，指向右节点的指向右节点
root.left=trimBST(root.left,low,high)；
root.right=trimBST(root.right,low,high);
//返回root重新指向的节点
return root;
}
}
108. 将有序数组转换为二叉搜索树（简单）*
题目：leetcode：108. 将有序数组转换为二叉搜索树
思路：
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//左闭右闭区间
return ss(nums,0,nums.length-1);
}
public TreeNode ss(int []nums,int left,int right){
//如果left大于right，先返回null节点
if(left>right)return null;
//二分查找其节点，本身就是有序，所以通过左边的节点勾选左子树，右边的节点勾选右子树
int mid=left+(right-left)/2;
//本身就没有子树结构，所以要创建
TreeNode root=new TreeNode(nums[mid]);
root.left=ss(nums,left,mid-1);
root.right=ss(nums,mid+1,right);
return root;
}
}
538. 把二叉搜索树转换为累加树（中等）
题目：leetcode：538. 把二叉搜索树转换为累加树
大致如下如下：
思路：
class Solution {
//定义一个计数
int sum=0;
//此处的累加树，其实就是反中序遍历
public TreeNode convertBST(TreeNode root) {
//如果为空，则返回空节点
if(root==null)return null;
convertBST(root.right);
//具体在于处理根节点，累加完之后，要存放回根节点
sum+=root.val;
root.val=sum;
convertBST(root.left);
return root;
}
}
