第六章 二叉树 part06
今日内容 ● 654.最大二叉树
● 617.合并二叉树
● 700.二叉搜索树中的搜索
● 98.验证二叉搜索树 详细布置 654.最大二叉树 又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历 题目链接/文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1MG411G7ox 617.合并二叉树 这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。题目链接/文章讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK 700.二叉搜索树中的搜索 递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html
视频讲解：https://www.bilibili.com/video/BV1wG411g7sF 98.验证二叉搜索树 遇到 搜索树，一定想着中序遍历，这样才能利用上特性。 但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。题目链接/文章讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV18P411n7Q4
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息目录
0654_最大二叉树
0617_合并二叉树
0700_二叉搜索树中的搜索
0098_验证二叉搜索树
0654_最大二叉树
根据数组构造二叉树
- 106.从中序与后序遍历序列构造二叉树
- 105.从前序与中序遍历序列构造二叉树
- 654.最大二叉树
java">package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;public class _0654_最大二叉树 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0654 {public TreeNode constructMaximumBinaryTree(int[] nums) {return compute(nums, 0, nums.length);}private TreeNode compute(int[] nums, int leftIndex, int rightIndex) {if (rightIndex - leftIndex < 1) {//没有元素了return null;}if (rightIndex - leftIndex == 1) {return new TreeNode(nums[leftIndex]);}int maxValue = nums[leftIndex], maxIndex = leftIndex;for (int i = leftIndex + 1; i < rightIndex; i++) {if (maxValue < nums[i]) {maxValue = nums[i];maxIndex = i;}}TreeNode leftNode = compute(nums, leftIndex, maxIndex);TreeNode rightNode = compute(nums, maxIndex + 1, rightIndex);return new TreeNode(maxValue, leftNode, rightNode);}
}class Solution0654_2 {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;}
}class Solution0654_3 {public TreeNode constructMaximumBinaryTree(int[] nums) {return construct(nums, 0, nums.length - 1);}public TreeNode construct(int[] nums, int left, int right) {if (left > right) {return null;}int best = left;for (int i = left + 1; i <= right; ++i) {if (nums[i] > nums[best]) {best = i;}}TreeNode node = new TreeNode(nums[best]);node.left = construct(nums, left, best - 1);node.right = construct(nums, best + 1, right);return node;}
}0617_合并二叉树
java">package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class _0617_合并二叉树 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0617 {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;}public TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {if (t1 == null) {return t2;}if (t2 == null) {return t1;}TreeNode merged = new TreeNode(t1.val + t2.val);merged.left = mergeTrees2(t1.left, t2.left);merged.right = mergeTrees2(t1.right, t2.right);return merged;}
}class Solution0617_2 {//递归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;}//使用栈迭代public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {if (root1 == null) {return root2;}if (root2 == null) {return root1;}Stack<TreeNode> stack = new Stack<>();stack.push(root2);stack.push(root1);while (!stack.isEmpty()) {TreeNode node1 = stack.pop();TreeNode node2 = stack.pop();node1.val += node2.val;if (node2.right != null && node1.right != null) {stack.push(node2.right);stack.push(node1.right);} else {if (node1.right == null) {node1.right = node2.right;}}if (node2.left != null && node1.left != null) {stack.push(node2.left);stack.push(node1.left);} else {if (node1.left == null) {node1.left = node2.left;}}}return root1;}//使用队列迭代public TreeNode mergeTrees3(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;}
}0700_二叉搜索树中的搜索
解决二叉树题目，优先使用递归。
递归法
1.确定递归函数的参数和返回值；
2.确定终止条件；
3.确定单层递归的逻辑。
java">package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;public class _0700_二叉搜索树中的搜索 {
}class Solution0700 {//递归，普通二叉树public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) {return root;}TreeNode left = searchBST(root.left, val);if (left != null) {return left;}return searchBST(root.right, val);}
}class Solution0700_2 {//递归，利用二叉搜索树特点，优化public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) {return root;}if (val < root.val) {return searchBST(root.left, val);} else {return searchBST(root.right, val);}}
}class Solution0700_3 {//迭代，普通二叉树public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) {return root;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode pop = stack.pop();if (pop.val == val) {return pop;}if (pop.right != null) {stack.push(pop.right);}if (pop.left != null) {stack.push(pop.left);}}return null;}public TreeNode searchBST2(TreeNode root, int val) {Deque<TreeNode> deque = new LinkedList<>();deque.offer(root);while (!deque.isEmpty()) {TreeNode poll = deque.poll();if (poll != null && poll.val == val) {return poll;}if (poll.val < val && poll.right != null) {deque.offer(poll.right);} else if (poll.val > val && poll.left != null) {deque.offer(poll.left);}}return null;}
}class Solution0700_4 {//迭代，利用二叉搜索树特点，优化，可以不需要栈public TreeNode searchBST(TreeNode root, int val) {while (root != null)if (val < root.val) root = root.left;else if (val > root.val) root = root.right;else return root;return null;}
}0098_验证二叉搜索树
java">package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class _0098_验证二叉搜索树 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0098 {List<Integer> list = new ArrayList<Integer>();public boolean isValidBST(TreeNode root) {if (root == null) {return true;}inOrder(root);//将 ArrayList 转换为 int 数组int[] intArray = list.stream().mapToInt(Integer::intValue).toArray();for (int i = 0; i < intArray.length - 1; i++) {if (intArray[i] >= intArray[i + 1]) {return false;}}return true;//Object[] array1 = list.toArray();
// List<Integer> list2 = list;
// Collections.sort(list2);
// if (list.toString().equals(list2.toString())) {
// return true;
// } else {
// return false;
// }}private void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);list.add(root.val);inOrder(root.right);}
}//使用统一迭代法
class Solution0098_2 {//使用统一迭代法public boolean isValidBST(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;if (root != null)stack.add(root);while (!stack.isEmpty()) {TreeNode curr = stack.peek();if (curr != null) {stack.pop();if (curr.right != null)stack.add(curr.right);stack.add(curr);stack.add(null);if (curr.left != null)stack.add(curr.left);} else {stack.pop();TreeNode temp = stack.pop();if (pre != null && pre.val >= temp.val)return false;pre = temp;}}return true;}
}class Solution0098_3 {// 递归TreeNode max;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 左boolean left = isValidBST(root.left);if (!left) {return false;}// 中if (max != null && root.val <= max.val) {return false;}max = root;// 右boolean right = isValidBST(root.right);return right;}
}class Solution0098_4 {// 迭代public boolean isValidBST(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;// 左}// 中，处理TreeNode pop = stack.pop();if (pre != null && pop.val <= pre.val) {return false;}pre = pop;root = pop.right;// 右}return true;}
}// 简洁实现·递归解法
class Solution0098_5 {public boolean isValidBST(TreeNode root) {return validBST(Long.MIN_VALUE, Long.MAX_VALUE, root);}boolean validBST(long lower, long upper, TreeNode root) {if (root == null) return true;if (root.val <= lower || root.val >= upper) return false;return validBST(lower, root.val, root.left) && validBST(root.val, upper, root.right);}
}// 简洁实现·中序遍历
class Solution0098_6 {private long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left)) {return false;}if (root.val <= prev) { //不满足二叉搜索树条件return false;}prev = root.val;return isValidBST(root.right);}
}class Solution0098_7 {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode node, long lower, long upper) {if (node == null) {return true;}if (node.val <= lower || node.val >= upper) {return false;}return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);}
}
