654. 最大二叉树
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums.length == 0) return null;
// 找最大值及其下标（优化点：寻找最大值）
int rootVal = Integer.MIN_VALUE;
int rootIdx = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > rootVal) {
rootVal = nums[i];
rootIdx = i;
}
}
TreeNode root = new TreeNode(rootVal);
// 优化点：用下标代替创建新数组
root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, rootIdx));
root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, rootIdx + 1, nums.length));
return root;
}
}部分优化
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return traversal(nums, 0, nums.length);
}
// 使用同一个数组，不用每次生成新数组
public TreeNode traversal(int[] nums, int left, int right) {
if (left >= right) return null;
// 待优化
int rootVal = Integer.MIN_VALUE;
int rootIdx = -1;
for (int i = left; i < right; i++) {
if (nums[i] > rootVal) {
rootVal = nums[i];
rootIdx = i;
}
}
TreeNode root = new TreeNode(rootVal);
root.left = traversal(nums, left, rootIdx);
root.right = traversal(nums, rootIdx + 1, right);
return root;
}
}617. 合并二叉树
深度优先遍历即可，但是要注意递归结束条件，当两个节点均为空时才确定返回 null，只要有一个节点不为空，就能继续递归下去。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return null;
int root1Val = root1 == null ? 0 : root1.val;
int root2Val = root2 == null ? 0 : root2.val;
TreeNode node = new TreeNode(root1Val + root2Val);
// 递归时，空节点取 null 就行
node.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
node.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
return node;
}
}上面的做法是创建了新节点，还有一种修改和复用已有节点的做法，代码更精简些。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// root1 为空，就返回 root2，即便 root2 为空也满足条件，下面同理
if (root1 == null) return root2;
if (root2 == null) return root1;
// 复用 root1 的节点，root2 也行
root1.val = root1.val + root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}// 迭代法
if (root1 == null) return root2;
if (root2 == null) return root1;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root1);
q.offer(root2);
while (!q.isEmpty()) {
TreeNode n1 = q.poll();
TreeNode n2 = q.poll();
n1.val = n1.val + n2.val;
if (n1.left != null && n2.left != null) {
q.offer(n1.left);
q.offer(n2.left);
}
if (n1.right != null && n2.right != null) {
q.offer(n1.right);
q.offer(n2.right);
}
// 如果 n1 没有 left，直接将 n2.left 拿过来
// 后面的节点直接不需要遍历了
if (n1.left == null && n2.left != null) {
n1.left = n2.left;
}
// 如果 n1 没有 right，直接将 n2.right 拿过来
// 后面的节点直接不需要遍历了
if (n1.right == null && n2.right != null) {
n1.right = n2.right;
}
}
return root1;700. 二叉搜索树中的搜索
// 递归法
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) {
return root;
} else if (root.val > val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}// 迭代法
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
Stack<TreeNode> st = new Stack<>();
st.push(root);
while (!st.isEmpty()) {
TreeNode node = st.pop();
if (node.val == val) {
return node;
} else if (node.val > val && node.left != null) {
st.push(node.left);
} else if (node.val < val && node.right != null) {
st.push(node.right);
}
}
return null;
}
}// 迭代法2
// 因为二叉搜索树是有序的，沿着某条路径查下去即可，
// 所以不需要全部遍历，没有回溯，不需要额外的栈辅助空间
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
// 让 root 一直找下去即可
while (root != null) {
if (root.val == val) {
return root;
} else if (val < root.val) {
root = root.left;
} else {
root = root.right;
}
}
return null;
}
}98. 验证二叉搜索树
二叉搜索树的特性：中序遍历序列是有序的。因此只要我们判断中序遍历序列是否有序即可。一种方法是生成遍历序列，然后使用双指针（或者记录此前的最大值）判断数组是否是递增的。一种方法是直接在中序遍历过程中使用双指针，判断节点值是否是递增的。所以重点在于如何判断递增。
// 方法 1
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new LinkedList<>();
traversal(root, list);
// List 转为整型数组
Integer[] arr = list.toArray(new Integer[0]);
if (arr.length == 0) return true;
// 判断数组是否有序的方法
int prev = -1;
for (int i = 0; i < arr.length; i++) {
if (prev != -1 && arr[prev] >= arr[i]) return false;
prev = i;
}
return true;
}
// 中序遍历，获得中序遍历序列
public void traversal(TreeNode root, List<Integer> list) {
if (root == null) return;
traversal(root.left, list);
list.add(root.val);
traversal(root.right, list);
}
}// 方法 2
class Solution {
// 记录前一个结点
private TreeNode prev;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
boolean left = isValidBST(root.left);
// 如果前一个节点值大，则不满足顺序，直接返回 false
if (prev != null && root.val <= prev.val) return false;
// 否则更新 prev
prev = root;
boolean right = isValidBST(root.right);
return left && right;
}
}