继续好商会网站建设,wordpress主题图片路径,湖南网络推广公司,ui设计需要学什么软件最大二叉树
题目详细#xff1a;LeetCode.654
这道题在题目几乎就说明了解题的思路了#xff1a;
创建一个根节点#xff0c;其值为 nums 中的最大值#xff1b;递归地在最大值左边的子数组上构建左子树#xff1b;递归地在最大值右边的子数组上构建右子树#xff1b;…最大二叉树
题目详细LeetCode.654
这道题在题目几乎就说明了解题的思路了
创建一个根节点其值为 nums 中的最大值递归地在最大值左边的子数组上构建左子树递归地在最大值右边的子数组上构建右子树返回 nums 构建的 最大二叉树 。
显而易见我可以把构建最大二叉树这个大问题划分为一个个小问题当每一棵子树都按照上述思路来构建那么整体就构成了一棵最大二叉树小问题思路如下
数组 nums 有三种情况 数组长度为0说明节点序列为空返回 null数组长度为1说明只有一个节点构建并返回节点数组长度 1找出最大值来构建当前节点 找出nums中的最大值以及最大值的下标按照要求通过最大值的下标来划分构建左右子树的子数组左子树通过最大值左边的子数组来构建右子树通过最大值右边的子数组来构建
递归从根节点开始到左右子树构建子树最后返回构建完成的根节点。
Java解法递归深度优先遍历
class Solution {public int findMaxIndex(int[] nums){int res -1, max -1;for(int i 0; i nums.length; i){if(max nums[i]){max nums[i];res i;}}return res;}public TreeNode constructMaximumBinaryTree(int[] nums) {if(nums.length 0)return null;if(nums.length 1)return new TreeNode(nums[0]);int max_i this.findMaxIndex(nums);TreeNode root new TreeNode(nums[max_i]);root.left this.constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, max_i));root.right this.constructMaximumBinaryTree(Arrays.copyOfRange(nums, max_i1, nums.length));return root;}
}合并二叉树
题目详细LeetCode.617
通过合并二叉树的过程不难发现在合并过程中会出现这4种情况这里将要合并的树记作 root1 和 root2让root2合并到root1
root1 ! null root2 ! null那么两个节点的值相加root1.val root2.val;root1 null root2 ! null左节点为空那么直接将 root2 合并到 root1 中root1 ! null root2 null右节点为空那么无需合并直接返回左节点root1 null root2 null左右节点都为空无需合并或二叉树已完成合并
递归从根节点到左右子树开始合并子树最后返回合并完成的根节点root1。
Java解法递归深度优先遍历
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 null){// root1 ! null root2 ! nullreturn root2;}else if(root2 null){// root1 null root2 ! nullreturn root1;}// root1 ! null root2 nullroot1.val root2.val;root1.left mergeTrees(root1.left, root2.left);root1.right mergeTrees(root1.right, root2.right);return root1;}
}二叉搜索树中的搜索
题目详细LeetCode.700
二叉搜索树的特点可以简要概括为
从根节点开始构建一棵二叉树使其每一棵子树都满足 左节点的值 父节点的值右节点的值 父节点的值 【注意】所以一棵真正的二叉搜索树应满足 左子树上所有的节点值都 父节点的值右子树上所有的节点值都 父节点的值 那么我们则称这棵树为二叉搜索树
那么这道题要求在二叉搜索树中找到目标值对应的子树利用二叉搜索树的特点和递归来解题就非常清晰易懂了在搜索过程中会遇到这3种情况
节点为空则二叉树中不到目标值节点返回null节点的值 目标值说明目标值只可能在二叉搜索树的右子树出现递归搜索右子树节点的值 目标值说明目标值只可能在二叉搜索树的左子树出现递归搜索左子树节点的值 目标值说明当前节点就是我们要找的子树的根节点返回该节点
Java解法递归深度优先遍历
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(null root) return null;if(val root.val){return searchBST(root.left, val);}else if(val root.val){return searchBST(root.right, val);}// val root.valreturn root;}
}验证二叉搜索树
题目详细LeetCode.98
Java错误的解法陷进了一个大坑
class Solution {public boolean isValidBST(TreeNode root) {return this.dfs(root.left, root.val, true) this.dfs(root.right, root.val, false);}public boolean dfs(TreeNode root, int father_val, boolean is_left){if(root null) return true;boolean flag false;if(is_left){flag root.val father_val}else{flag root.val father_val}return flag this.dfs(root.left, root.val, true) this.dfs(root.right, root.val, false);}
}一开始我发现这道题很简单不就是根据二叉搜索树的特点来验证一棵二叉树是不是搜索树么然后就得出结论
递归验证每一个树的节点是否满足二叉搜索树的特点二叉搜索树的特点在上一题有讲述这里就不做赘述了如果每一个节点都满足那么则视作整体满足返回 true
接着写完我就非常自信地提交了答案很好错误的测试例子出现了 验证了一下算法发现到达节点值为3的节点时应该返回 false因为假如构建一棵二叉搜索树的话节点3应该是节点4的左节点才对。
所以
不能单纯地对每一个节点判断其是否满足左节点 父节点右节点 父节点就完事了。一棵真正的二叉搜索树还需要满足的条件是左子树所有节点 父节点右子树所有节点 父节点。
从二叉搜索树的特点还可以发现其中序遍历序列是一个递增序列那么解题方法忽如一夜春风来千树万树梨花开呀
解法一 我们可以直接对该二叉树进行中序遍历获取该树的中序遍历序列判断该遍历序列是否是递增的如果是递增序列则说明该树是二叉搜索树否则不是。
Java解法中序遍历验证二叉搜索树的中序遍历序列是否是递增序列
class Solution {ListInteger inorder_list new ArrayList();public void dfs(TreeNode root){if(root null) return;dfs(root.left);inorder_list.add(root.val);dfs(root.right);}public boolean isValidBST(TreeNode root) {this.dfs(root);int pre Integer.MIN_VALUE;for(int i: this.inorder_list){if(pre i) return false;pre i;}return true;}
}解法二 从解法一可知我们可以通过验证中序遍历序列是否递增进而判断该树是否为二叉搜索树那么我们也可以模拟这一思想改用迭代的算法能够一边遍历节点一边处理节点一边迭代遍历二叉树一边比较与前一个遍历的值来判断遍历序列是否有序进而判断该树是否为二叉树
Java解法中序遍历模拟迭代一边遍历一边比较
class Solution {public boolean inorder(TreeNode root){StackTreeNode stack new Stack();if(null ! root) stack.push(root);TreeNode pre null;while(!stack.isEmpty()){TreeNode node stack.pop();if(null ! node){// 以右根左的顺序进栈出栈顺序为左根右if(null ! node.right) stack.push(node.right);stack.push(node);stack.push(null);if(null ! node.left) stack.push(node.left);}else{node stack.pop();if(null ! pre node.val pre.val) return false;pre node;}}return true;}public boolean isValidBST(TreeNode root) {return this.inorder(root);}
}天下事有难易乎为之则难者亦易矣不为则易者亦难矣。人之为学有难易乎学之则难者亦易矣不学则易者亦难矣。 天下的事情有困难和容易的区别吗只要肯做那么困难的事情也变得容易了如果不做那么容易的事情也变得困难了。人们做学问有困难和容易的区别吗只要肯学那么困难的学问也变得容易了如果不学那么容易的学问也变得困难了。
这首诗出自清代彭端淑的《为学一首示子侄》最近我一直在努力学习但又一直感觉自己为面试的准备工作很不充分不敢大胆投简历也不敢去面试看完这首诗之后恍然大悟
“世上无难事只怕有心人。”亦是同样的道理困难是可以克服的慢慢来吧。
