高仿做的好点的网站,网页设计实训报告题目来源,做文案策划需要知道些什么网站,怎么做m开头的网站题目与题解
654.最大二叉树 题目链接#xff1a;654.最大二叉树 代码随想录题解#xff1a;654.最大二叉树 视频讲解#xff1a;又是构造二叉树#xff0c;又有很多坑#xff01;| LeetCode#xff1a;654.最大二叉树_哔哩哔哩_bilibili 解题思路#xff1a; 构造最大二… 题目与题解
654.最大二叉树 题目链接654.最大二叉树 代码随想录题解654.最大二叉树 视频讲解又是构造二叉树又有很多坑| LeetCode654.最大二叉树_哔哩哔哩_bilibili 解题思路 构造最大二叉树递归非常合适。入参是用于构造的数组返回值是构造结束后的根结点终止条件是当前结点为空。递归体为首先遍历数组找到数组中最大值及其所在的位置然后定义两个新数组一个包含最大值左边所有数用于构造左子树一个包含最大值右边所有数用于构造右子树然后分别将两个数组输入最大二叉树构造方法构造对应根结点的左右子树。
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {if (nums.length 0) return null;int maxIndex 0;int max nums[0];for (int i 1; i nums.length; i) {if (nums[i] max) {maxIndex i;max nums[i];}}int[] leftNums new int[maxIndex];for (int i 0; i maxIndex; i) {leftNums[i] nums[i];}int[] rightNums new int[nums.length - maxIndex - 1];for (int i maxIndex 1; i nums.length; i) {rightNums[i - maxIndex - 1] nums[i];}TreeNode node new TreeNode(max, constructMaximumBinaryTree(leftNums), constructMaximumBinaryTree(rightNums));return node;}
}
看完代码随想录之后的想法 思路跟随想录第二个方法是一致的第一个方法略有点复杂还需要多加一次判断和取值先pass。 写法上我还有待改进因为不想写多余的递归函数所以就直接使用该函数为递归体了但是也造成每次调用的时候都要new两个新的数组效率会降低Java不像C可以直接传地址。像答案里面调用的递归函数入参写成原数组和头尾index就比较方便。此外只有一个元素时可以提前判断返回这样也不需要额外再求一次最大值和构建左右子树的数组了。
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]);}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.合并二叉树 视频讲解一起操作两个二叉树有点懵| LeetCode617.合并二叉树_哔哩哔哩_bilibili 解题思路 操作两个树和操作一个树的方法其实差不多递归每次同时传入位置相同的结点就行。因此递归的入参为两个树相同位置的子树根结点返回值为合并后的根节点终止条件是两个结点都为空。递归体为如果两个结点都为空不做操作直接返回null如果其中一个结点为空直接返回非空结点如果都不为空则new一个新的结点其值为两个结点值之和左子树和右子树都分别调用当前函数入参分别为两个结点的左子树和右子树最后返回该新结点。
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 null root2 null) return null;else if (root1 ! null root2 null) {return root1;} else if (root1 null root2 ! null) {return root2;} else {return new TreeNode(root1.val root2.val,mergeTrees(root1.left, root2.left),mergeTrees(root1.right, root2.right));}}
}
看完代码随想录之后的想法 递归法思路一致迭代法也比较好理解有符合条件的左右子树才加入队列否则直接赋值避免了队列中的元素有重复或者缺漏。不过写起来有些麻烦就看看吧。
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2;if (t2 NULL) return t1;queueTreeNode* que;que.push(t1);que.push(t2);while(!que.empty()) {TreeNode* node1 que.front(); que.pop();TreeNode* node2 que.front(); que.pop();// 此时两个节点一定不为空val相加node1-val node2-val;// 如果两棵树左节点都不为空加入队列if (node1-left ! NULL node2-left ! NULL) {que.push(node1-left);que.push(node2-left);}// 如果两棵树右节点都不为空加入队列if (node1-right ! NULL node2-right ! NULL) {que.push(node1-right);que.push(node2-right);}// 当t1的左节点 为空 t2左节点不为空就赋值过去if (node1-left NULL node2-left ! NULL) {node1-left node2-left;}// 当t1的右节点 为空 t2右节点不为空就赋值过去if (node1-right NULL node2-right ! NULL) {node1-right node2-right;}}return t1;}
};
遇到的困难 无
700.二叉搜索树中的搜索 题目链接700.二叉搜索树中的搜索 代码随想录题解700.二叉搜索树中的搜索 视频讲解不愧是搜索树这次搜索有方向了| LeetCode700.二叉搜索树中的搜索_哔哩哔哩_bilibili 解题思路 二叉搜索树本身就是通过一定的排序构造的所以搜索效率极高。一般二叉搜索树的左子树所有结点比根结点小右子树的所有结点比根结点大所以搜索的时候只要通过递归或者迭代的方式每层比较一次就可以快速找到结果了。
递归法入参为当前根结点和待搜索的值返回值是布尔值表示搜到与否终止条件是搜到结果或当前结点为空即不存在符合条件的值。递归体为如果当前结点的值等于目标值直接返回true如果当前结点值小于目标值继续搜索该结点右子树否则搜索该结点左子树。
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);}
}
迭代法按层序遍历的思路用队列保存符合要求的结点如果队首结点的值等于目标值直接返回true如果队首结点值小于目标值将其右结点加入队列否则将其左结点加入队列直到队列为空返回false。
class Solution {public TreeNode searchBST(TreeNode root, int val) {// 迭代队列版if (root null || root.val val) return root;QueueTreeNode q new LinkedList();q.add(root);while (!q.isEmpty()) {TreeNode node q.poll();if (val node.val) return node;if (val node.val node.left ! null) q.add(node.left);if (val node.val node.right ! null) q.add(node.right);}return null;}
}
看完代码随想录之后的想法 递归法是一样的但是迭代法写复杂了事实上都不需要队列或者栈去存数字只要像链表那样一层一层直接往下搜索就好非常简单。
class Solution {public TreeNode searchBST(TreeNode root, int val) {// 迭代极简版if (root null || root.val val) return root;if (val root.val) root root.left;else root root.right;return searchBST(root, val);}
}
遇到的困难 基础题不难写
98.验证二叉搜索树 题目链接98.验证二叉搜索树 代码随想录题解98.验证二叉搜索树 视频讲解你对二叉搜索树了解的还不够 | LeetCode98.验证二叉搜索树_哔哩哔哩_bilibili 解题思路 一开始想用递归完成利用二叉搜索树的性质比较每个树根节点的值和其左右结点的值如果左结点小于根结点右结点大于根结点该节点就符合要求继续递归的判断左右子树是否符合要求即可。 但是这样做会出错原因是二叉搜索树要求的是左子树的每一个结点都小于根结点右子树的每一个结点都大于根结点只满足一层是不够的。然后看了一下leetcode上给的题解用了一个新的递归函数入参是当前节点和历史最大值及最小值返回值是布尔值表示树是否是二叉搜索树终止条件为当前结点为空或者其值比历史最小值小或比历史最大值大。递归体为将当前节点的左右子树根结点分别放入递归函数放左子树时其输入的历史最大值为当前根结点的值放右子树时其输入的历史最小值为当前根结点的值。
class Solution {TreeNode pre;public boolean isValidBST(TreeNode root) {if (root null) return true;return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode root, long min, long max) {if (root null) return true;if (root.val min || root.val max) return false;return isValidBST(root.left, min, root.val) isValidBST(root.right, root.val, max);}
}
看完代码随想录之后的想法 代码随想录给出的前序遍历得到数组判断该数组是否是递增数组的思路很清晰虽然多了空间复杂度但是很好理解。
// 简洁实现·中序遍历
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);}
} 另一种递归只记录了用最大值去判断是否符合要求着实是有点看不懂了还是跳过吧。
遇到的困难 第一次写完上传的时候就调入了陷阱二叉搜索树的定义没有理解透彻碰到不符合要求的树就出错了。参考答案写出含上下限的递归函数后又因为测试用例里面包含了Integer的最大值和最小值与初始化的值相同了所以再次出错仔细看了答案以后发现用的是long而非int变量这样就不会有边界问题。也是蛮tricky的。
今日收获 再次加深了一下二叉树的印象学习二叉搜索树的定义和用法。递归函数的选择真的很奇妙好好学习。
