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
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums.length == 0) return null;
int max = -1, index = 0;
for(int i = 0; i < nums.length; i ++){
if(nums[i] > max){
max = nums[i];
index = i;
}
}
TreeNode root = new TreeNode(max);
if(nums.length == 1) return root;
int[] left = sub(nums, 0, index);
int[] right = sub(nums, index + 1, nums.length);
root.left = constructMaximumBinaryTree(left);
root.right = constructMaximumBinaryTree(right);
return root;
}
public int[] sub(int[] array, int start, int end){
int[] res = new int[end - start];
int r = 0;
for(int i = start; i < end; i ++){
res[r ++] = array[i];
}
return res;
}
}
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
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null) return root2;
if(root2 == null) return root1;
if(root1 == null && root2 == null) return null;
TreeNode cur = new TreeNode(root1.val + root2.val);
TreeNode left = mergeTrees(root1.left, root2.left);
TreeNode right = mergeTrees(root1.right, root2.right);
cur.left = left;
cur.right = right;
return cur;
}
}
700.二叉搜索树中的搜索
递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性
视频讲解：https://www.bilibili.com/video/BV1wG411g7sF
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null) return null;
if(root.val == val) return root;
TreeNode left = searchBST(root.left, val);
TreeNode right = searchBST(root.right, val);
if(left != null) return left;
if(right != null) return right;
return null;
}
}
class Solution {
// 递归，普通二叉树
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 Solution {
// 递归，利用二叉搜索树特点，优化
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 Solution {
// 迭代，普通二叉树
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;
}
}
class Solution {
// 迭代，利用二叉搜索树特点，优化，可以不需要栈
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;
}
}
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
应该确保左子树的最大值小于根节点的值，且根节点的值小于右子树的最小值。
我的
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
if(root.left == null && root.right == null) return true;
boolean left = isValidBST(root.left);
boolean right = isValidBST(root.right);
if(root.left == null) return root.val < root.right.val && right;
if(root.right == null) return root.left.val < root.val && left;
boolean mid = root.left.val < root.val && root.val < root.right.val;
return left && mid && right;
}
}
root =
[5,4,6,null,null,3,7]
添加到测试用例
输出
true
预期结果
false
classSolution{// 递归TreeNodemax;publicbooleanisValidBST(TreeNoderoot){if(root==null){returntrue;}// 左booleanleft=isValidBST(root.left);if(!left){returnfalse;}// 中if(max!=null&&root.val<=max.val){returnfalse;}max=root;// 右booleanright=isValidBST(root.right);returnright;}}classSolution{// 迭代publicbooleanisValidBST(TreeNoderoot){if(root==null){returntrue;}Stack<TreeNode>stack=newStack<>();TreeNodepre=null;while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;// 左}// 中，处理TreeNodepop=stack.pop();if(pre!=null&&pop.val<=pre.val){returnfalse;}pre=pop;root=pop.right;// 右}returntrue;}}
