二叉树 part06
- 654.最大二叉树
- 解题思路
- 617.合并二叉树
- 解题思路
- 700.二叉搜索树中的搜索
- 解题思路
- 98.验证二叉搜索树
- 解题思路
- 误区
654.最大二叉树
又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历
题目链接/文章讲解：654.最大二叉树
视频讲解：654.最大二叉树
解题思路
和昨天最后2道题思路类似，比那2道题处理起来还更简单一些
解题步骤：
- 递归终止条件判断：只有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]); //只有1个元素表明到了叶子节点
// 找最大值及最大值所在位置
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.合并二叉树
视频讲解：617.合并二叉树 ## 解题思路
解题思路
考查同时对两个二叉树同时操作
理论上前中后序遍历都可以，层序迭代也可以。但是leecode要求必须从根节点开始合并，所以只能用前序或者层序。
思路：
- 终止条件：两棵树遍历的当前节点至少有一个为null
- 单层递归逻辑：把两棵树的值加到一起
// 递归 前序
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;
}
}
// 使用队列迭代
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;
}
}
700.二叉搜索树中的搜索
递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性
题目链接/文章讲解: 700.二叉搜索树中的搜索
视频讲解：700.二叉搜索树中的搜索
解题思路
二叉搜索树是一个有序树，它的递归遍历和迭代遍历和普通二叉树都不一样。
- 终止条件：root为空或者找到这个数值
- 单层递归逻辑：因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
如果root.val > val，搜索左子树，如果root.val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
// 递归
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) return root;
TreeNode result = null;
if(root.val > val) result = searchBST(root.left, val);
if(root.val < val) result = searchBST(root.right, val);
return result;
}
}
// 层序迭代
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.验证二叉搜索树
但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。
题目链接/文章讲解：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
解题思路
- 遇到 搜索树，一定想着中序遍历，这样才能利用上特性.如果中序遍历下元素是单调递增的，那它就是一颗二叉搜索树。
- 遍历二叉搜索树时，如何用两个指针比较元素大小。
误区
- 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
if (root->val > root->left->val && root->val < root->right->val) {
return true;
} else {
return false;
}
- 样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。此时可以初始化比较元素为longlong的最小值。但是这样解决不是最优的，可以用指针来进行比较
// 递归 中序遍历 定义TreeNode prev = null;
class Solution {
TreeNode prev = null;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
if(!isValidBST(root.left)) return false; // 左
// 中
if(prev != null && root.val <= prev.val) return false;
prev = root;
return isValidBST(root.right); // 右
}
}
// 递归 中序遍历 定义long prev
class Solution {
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); // 右
}
}
