资源引用：
刷题小记：
二叉树的操作方式非常丰富，是由遍历方式和二叉树共同决定的。
654.最大二叉树（654.最大二叉树）
题目分析：
递归构造一个以数组中最大元素为根节点、以其左子数组为左子树、以其右子数组为右子树的二叉树。
解题重点：
采用前序遍历，先构造根节点，再构造左右子树，最终递归实现。
解题思路：
- 递归的参数：对应该子树的数组
- 递归的返回值：构造完成后的该子树的根节点
- 递归的终止条件：递归参数的长度为1，直接返回用该元素构造根节点并返回
- 递归的单层递归逻辑：
-
- 找到参数数组中的最大的值和对应下标，构造根节点，利用下标分割左右数组
- 若左子数组不为空，利用左子数组递归构造左子树并返回左子树根节点
- 若右子数组不为空，利用右子数组递归构造右子树并返回右子树根节点
- 最终返回该子树根节点（已填充左右子树）
思路优化：递归传入的参数若为分割后的子数组，对空间占用较大且可能破坏原数组，因此通过传入分隔下标的方式来进行子数组提取
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree1(nums, 0, nums.length);
}
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
if (rightIndex - leftIndex < 1) {// 没有元素了
return null;
}
if (rightIndex - leftIndex == 1) {// 只有一个元素
return new TreeNode(nums[leftIndex]);
}
int maxIndex = leftIndex;// 最大值所在位置
int maxVal = nums[maxIndex];// 最大值
for (int i = leftIndex + 1; i < rightIndex; i++) {
if (nums[i] > maxVal){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxVal);
// 根据maxIndex划分左右子树
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
return root;
}
}617.合并二叉树（617.合并二叉树）
题目分析：
给定两个二叉树，欲按如下规则合并二者：如果两个节点重叠，则节点值相加作为合并后的新节点的值；否则不为null的节点将直接作为新二叉树的节点。
解题重点：
构造新二叉树，需从根节点开始，故考虑前序遍历。
因同时操作两棵二叉树，故同时传入两棵二叉树的根节点，进行同步遍历。
解题思路：
- 遍历的参数：tree1根节点root1，tree2根节点root2
- 遍历的返回值：新二叉树的根节点
- 遍历的终止条件：
-
- root1为空，返回root2
- root2为空，返回root1
- （已经包含了root1和root2同时为空的情况，即最终返回null）
- 遍历的单层递归逻辑：
-
- （直接在tree1上做合并）合并root1和root2为新根节点root（即root1）
- （直接在tree1上做合并）递归root1和root2的左子树，得到新的左子树根节点left
- （直接在tree1上做合并）递归root1和root2的右子树，得到新的右子树根节点right
- 最终返回tree1的root1
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}700.二叉搜索树中的搜索（700.二叉搜索树中的搜索）
题目分析：
给定一棵二叉搜索树，其特性为：若任意节点的左子树不为空，则左子树上所有节点的值小于其根节点；若任意节点的右子树不为空，则右子树上所有节点的值大于其根节点。（二叉搜索树定义）
现从二叉搜索树中查找是否存在节点值为给定的值的节点，若存在则返回以该节点为根节点的子树，否则返回null。
解题重点：
由二叉搜索树的特性，我们考虑类似前序遍历的方式进行遍历。
解题思路：
使用迭代法解决：
- 迭代的循环条件：当前节点不为空
- 迭代逻辑：
-
- 若节点值小于给定值val，则更新节点为当前节点的右孩子
- 若节点值大于给定值val，则更新节点为当前节点的左孩子
- 若节点值等于给定值val，返回当前节点（或结束迭代）
- 迭代循环结束，返回null（或返回root）。
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while (root != null) {
if (root.val < val) root = root.right;
else if (root.val > val) root = root.left;
else break;
}
return root;
}
}98.验证二叉搜索树（98.验证二叉搜索树）
题目分析：
给定一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。由于carl哥说这题有坑，所以我们仔细分析一下“有效”的定义：
- 节点的左子树只包含小于当前节点的数（节点的左子树的任意节点值均小于根节点值）
- 节点的右子树只包含小于当前节点的数（节点的右子树的任意节点值均小于根节点值）
- 所有左子树和右子树自身必须也是二叉搜索树
符合二叉搜索树的基本定义。
解题重点：
借助二叉搜索树的特性，考虑使用中序遍历，所得遍历序列显然为递增序列，显然简化了遍历思路：
解题思路：
采用中序遍历的递归解决：
- 递归的参数：当前子树的根节点
- 递归的返回值：是否符合有效的二叉搜索树
- 递归的终止条件：若当前子树的根节点为空，则遍历结束，返回true
- 递归的单层递归逻辑：
-
- 先对该节点的左子树做递归判断得到左子树判断left
- 然后判断当前节点的值是否为当前遍历序列的最大值，若是则更新遍历序列最大值，否则返回false
- 接着对该节点的右子树做递归判断得到right
- 最后返回left和right的逻辑与
注意：由于测试样例中包含int型的最小值，故初始化遍历序列的最大值时，需要初始化为long型的小于-2^31的值。或者，可以通过记录前置节点的方式进行比较，该方法更简便。
class Solution {
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
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;
}
}