第一题：力扣617题
解题思路：
参照这篇
代码如下：
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;
}
}
第二题：力扣700题
解题思路：
根据二叉搜索树的特性做题，参见这篇
代码如下：
方式一：递归
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) {
return root;
}
//根据二叉搜索树的特点，来判断
//root的值大于给定的值，说明要找的值在root的左边，那我们就去左边接着找
if(root.val > val) {
return searchBST(root.left, val);
}
//同理
if(root.val < val) {
return searchBST(root.right, val);
}
return null;
}
}
方式二：迭代
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root != null) {
if(root.val > val) {
root = root.left;
} else if(root.val < val) {
root = root.right;
} else {
return root;
}
}
return null;
}
}
第三题：力扣98题
解题思路：
首先，BST是什么样子的？是有序的对不对；再联系一下我们遍历的二叉树方式，什么是有序的？是不是中序遍历。这个题我们只需判断中序遍历数组从左往右是不是单调递增的就完事了！
代码如下：
class Solution {
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
//最好不要用最大值变量来记录，因为我们不知道测试用例中最小值到底是int呢，还是long呢
//我们用一个指针记录一下前一个值就好了
if(root == null) {
return true;
}
boolean left = isValidBST(root.left);//判断左树
if(pre != null && pre.val >= root.val) {
return false;
}
pre = root;
boolean right = isValidBST(root.right);//判断右树
return left && right;
}
}
第四题：力扣530题
解题思路：
同样用到中序遍历+比较有序数组任意两个差的最小值
代码如下：
class Solution {
TreeNode pre = null;
int res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null) {
return 0;
}
traversal(root);
return res;
}
//遍历所有，不需要返回值
private void traversal(TreeNode t) {
if(t == null) {
return;
}
traversal(t.left);//左树
if(pre != null) {
res = Math.min(res, t.val - pre.val);//记录最小值
}
pre = t;//记录前一个位置
traversal(t.right);//右树
}
}
同样的还有几道题目：
力扣501题
力扣236题
力扣235题
力扣701题
第五题：力扣450题
解题思路：
参考大佬的思路，嘎嘎滴！！！
有以下五种情况：
第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
还得多和别人学习呀，自己这得花多长时间才能想的出来呀，呜呜呜
代码如下：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//1
if(root == null) {
return root;
}
if(root.val == key) {
//2
if(root.left == null && root.right == null) {
return null;
//3
} else if(root.left == null) {
return root.right;
//4
} else if(root.right == null) {
return root.left;
//5
} else {
TreeNode cur = root.right;
while(cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
}
}
if(root.val > key) {
root.left = deleteNode(root.left, key);
}
if(root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
}
同理，还有如下几个题：
力扣669题
第六题：力扣108题
解题思路：
这个题要比654题少了一个遍历树的过程，其他的没什么不同，也是从数组中间作为根节点开始组成新的树，根节点左边和根节点右边进行递归，直到满足数组left >= right（这是左闭右开的情况）。
代码如下：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//左闭右开
TreeNode root = traversal(nums, 0, nums.length);
return root;
}
private TreeNode traversal(int[] nums, int left, int right) {
if(left >= right) {
return null;
}
//此时只有一个，特判
if(right - left == 1) {
return new TreeNode(nums[left]);
}
int mid = left + ((right - left) / 2);
TreeNode root = new TreeNode(nums[mid]);
root.left = traversal(nums, left, mid);
root.right = traversal(nums, mid + 1, right);
return root;
}
}
第七题：力扣538题
解题思路：
什么是累加树？就是把一棵树按照右中左的顺序便利成一个数组，把这个数字依次相加起来，组成一个新的树，先右再中再左，okkk！
代码如下：
class Solution {
int pre;//定义一个参数记录cur前一个节点的值
public TreeNode convertBST(TreeNode root) {
pre = 0;
traversal(root);
return root;
}
private void traversal(TreeNode cur) {
if(cur == null) {
return;
}
traversal(cur.right);//右
cur.val = cur.val + pre;//中
pre = cur.val;
traversal(cur.left);//左
}
}
到这里二叉树专题就要先告一段落了。二刷的时候再回来看看自己做的题吧！哈哈哈