做图片站 把图片放到其它网站可以吗,wordpress高级企业自适应主题,沈阳网势科技有限公司怎么样,手机自建网站平台语言#xff1a;Java/C
654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。 …语言Java/C
654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树并且输出这个树的根节点。 示例 题目中说了输入的数组大小一定是大于等于1的所以我们不用考虑小于1的情况那么当递归遍历的时候如果传入的数组大小为1说明遍历到了叶子节点了。那么应该定义一个新的节点并把这个数组的数值赋给新的节点然后返回这个节点。
随后找当前整个数组的最大值根据最大值的下标将数组分为左子树和右子树继续递归进行构建。
class Solution {TreeNode traversal(int[] nums, int left, int right){if(right left ) return null; //判空if(right-left1){ //判断是否为一个节点左闭右开return new TreeNode(nums[left]);}int maxIdxleft;int maxValuenums[left];for(int ileft1;iright;i){if(nums[i]maxValue){maxValuenums[i];maxIdxi;}}TreeNode node new TreeNode(maxValue);node.lefttraversal(nums, left, maxIdx);node.righttraversal(nums, maxIdx1, right);return node;}public TreeNode constructMaximumBinaryTree(int[] nums) {return traversal(nums, 0, nums.length);}
}
617.合并二叉树 617.合并二叉树 给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 NULL 的节点将直接作为新二叉树的节点。 这道题我的第一个想法是建立一个哈希表层次遍历并存储第一个树的位置和值如果该位置没有节点则为-1随后创建新的节点遍历第二个树若当前位置已经有节点则将两个节点值相加返回如果第二棵树没有节点但第一棵树有则直接返回第一棵树的值如果第一棵树没有节点则直接返回第二棵树的值若第二棵树的节点数少于第一棵树则在遍历完第二棵树后直接将第一棵树的剩余节点返回。但是这个思路无疑增加了很多复杂性其实遍历两棵树和遍历一棵树的思路是一样的采用前序遍历即可。
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1null root2!null) return root2; if(root2null root1!null) return root1; if (root1 null root2 null) return null;TreeNode rootnew TreeNode(root1.valroot2.val);root.leftmergeTrees(root1.left,root2.left);root.rightmergeTrees(root1.right, root2.right);return root;}
} 700.二叉搜索树中的搜索 给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。 例如 因为本文的题设是二叉搜索树所以这题就相对好办了二叉搜索树是有序树
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树
因此找到值等于val的点然后递归返回从这个点以后的树即可
class Solution {TreeNode traversal(TreeNode root, int val){if(rootnull||root.valval) return root;if(root.valval){return traversal(root.left, val);}else{return traversal(root.right, val);}}public TreeNode searchBST(TreeNode root, int val) {return traversal(root, val);}
}
98.验证二叉搜索树 给定一个二叉树判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征 节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 考研时数据结构里有一个结论中序遍历下输出的二叉搜索树节点的数值是有序序列因此可以先将树转换为列表或数组再判断是否有序即可。注意在Java中如果将树转换为列表List则需要用.get和size()来获取列表的值和长度如果是数组因为不知道树的节点个数所以需要先设置一个很大的值所以也可以先将树转换为列表再将列表转换为数组。
class Solution {public void traversal(TreeNode root, ListInteger vec){if(rootnull) return;traversal(root.left, vec);vec.add(root.val);traversal(root.right, vec);}public boolean isValidBST(TreeNode root) {ListInteger resnew ArrayListInteger();traversal(root, res); // 将列表转换为数组Integer[] arrres.toArray(new Integer[res.size()]); for(int i1; iarr.length;i){if(arr[i]arr[i-1]) {return false; }}return true;}
}
