什么网站程序好,app界面设计开题报告,合肥制作网页设计,什么是可信网站认证代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第六章 二叉树 part06
今日内容 ● 654.最大二叉树
● 617.合并二叉树
● 700.二叉搜索树中的搜索
● 98.验证二叉搜索树 详细布置 654.最大二叉树 又是构造二叉树#xff0c;昨天大家刚刚做完 中序后序确定二叉树… 代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第六章 二叉树 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.最大二叉树 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_合并二叉树
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;}QueueTreeNode 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;}StackTreeNode 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;QueueTreeNode 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.确定单层递归的逻辑。 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;}StackTreeNode 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) {DequeTreeNode 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_验证二叉搜索树
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 {ListInteger list new ArrayListInteger();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();
// ListInteger 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) {StackTreeNode 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;}StackTreeNode 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);}
}
