Day17–二叉树–654. 最大二叉树，617. 合并二叉树，700. 二叉搜索树中的搜索，98. 验证二叉搜索树
654. 最大二叉树
- 方法一：Arrays.copyOfRange(nums, begin, end)——左闭右开
思路：
前序遍历。寻找子数组的区间。注意要形成“区间统一”的习惯。这里是左闭右开。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, findIndexOfMaxValue(nums));
}
private TreeNode build(int[] nums, int index) {
if (nums.length == 0) {
return null;
}
if (nums.length == 1) {
return new TreeNode(nums[0]);
}
TreeNode root = new TreeNode(nums[index]);
int[] leftArray = Arrays.copyOfRange(nums, 0, index);
int[] rightArray = Arrays.copyOfRange(nums, index + 1, nums.length);
root.left = build(leftArray, findIndexOfMaxValue(leftArray));
root.right = build(rightArray, findIndexOfMaxValue(rightArray));
return root;
}
private int findIndexOfMaxValue(int[] nums) {
int max = Integer.MIN_VALUE;
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
index = i;
}
}
return index;
}
}
- 方法二：原地复制，索引指示法
思路：
Arrays.copyOfRange每一层向下一层传递的都是一个新的数组。浪费空间时间。
向下传递索引值，可以省去复制的时间和空间。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length);
}
// 注意begin和end是左闭右开。[begin,end)
private TreeNode build(int[] nums, int begin, int end) {
// 没有元素了
if (end - begin < 1) {
return null;
}
// 只有一个元素
if (end - begin == 1) {
return new TreeNode(nums[begin]);
}
// 初始化最大值是begin索引的元素
int maxIndex = begin;
int maxValue = nums[begin];
// 寻找最大值和最大值索引
for (int i = begin + 1; i < end; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
maxIndex = i;
}
}
// 最大值索引为根
TreeNode root = new TreeNode(maxValue);
// 根据下标，递归寻找，拼接成左右子树
root.left = build(nums, begin, maxIndex);
root.right = build(nums, maxIndex + 1, end);
return root;
}
}
617. 合并二叉树
思路：
用栈迭代，前序遍历。
把node2的值加到node1上，如果一方是有节点一方是null，创建一个节点赋值为0补齐节点。
这个解法的操作是有点多余的，比如补齐0节点，判断一方为零时的操作。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 处理null情况
if(root1==null&&root2==null){
return null;
}
if(root1==null){
return root2;
}
if(root2==null){
return root1;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root2);
stack.push(root1);
while(!stack.isEmpty()){
TreeNode node1 = stack.pop();
TreeNode node2 = stack.pop();
node1.val += node2.val;
if(node1.left==null&&node2.left!=null){
node1.left = new TreeNode(0);
}else if(node1.left!=null&&node2.left==null){
node2.left = new TreeNode(0);
}
if(node1.left!=null&&node2.left!=null){
stack.push(node2.left);
stack.push(node1.left);
}
if(node1.right==null&&node2.right!=null){
node1.right = new TreeNode(0);
}else if(node1.right!=null&&node2.right==null){
node2.right = new TreeNode(0);
}
if(node1.right!=null&&node2.right!=null){
stack.push(node2.right);
stack.push(node1.right);
}
}
return root1;
}
}
思路：
修改版后的迭代法。如果有一方为null，直接等于另一边。
class Solution {
// 使用队列迭代
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
Queue<TreeNode> 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;
}
// 若node1的右节点为空，直接赋值
if (node1.right == null && node2.right != null) {
node1.right = node2.right;
}
}
return root1;
}
}
思路：
递归解法，合并到root1
class Solution {
// 递归解法，合并到root1
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;
}
}
递归解法，新建root
class Solution {
// 递归解法，新建root
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) {
return null;
}
// 找到了值，返回
if (val == root.val) {
return root;
}
// 目标值比它小，就搜左边
if (val < root.val) {
return searchBST(root.left, val);
} else {
// 目标值比它大，就搜右边
return searchBST(root.right, val);
}
}
}
上述代码的简化版：
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
return searchBST(val < root.val ? root.left : root.right, val);
}
}
思路：
迭代法：
class Solution {
// 迭代，利用二叉搜索树特点，优化，可以不需要栈
public TreeNode searchBST(TreeNode root, int val) {
TreeNode p = root;
while (p != null) {
if (val == p.val) {
return p;
}
if (val < p.val) {
p = p.left;
} else {
p = p.right;
}
}
// 走到这里，证明除了while循环，p为空。也可以直接写return null
return p;
}
}
98. 验证二叉搜索树
《代码随想录》
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
思路：
中序遍历
class Solution {
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
// root是null也是true
if (root == null) {
return true;
}
// 左
if (!isValidBST(root.left)) {
return false;
}
// 中
// 违反了二叉搜索树，一路向上返回false
if (pre >= root.val) {
return false;
}
// 更新“前节点”pre的值
pre = root.val;
// 右
if (!isValidBST(root.right)) {
return false;
}
return true;
}
}