本文主要是介绍Leetcoder Day17| 二叉树 part06,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
语言:Java/C++
654.最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。
示例 :
题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。
随后找当前整个数组的最大值,根据最大值的下标将数组分为左子树和右子树,继续递归进行构建。
class Solution {TreeNode traversal(int[] nums, int left, int right){if(right <= left ) return null; //判空if(right-left==1){ //判断是否为一个节点,左闭右开return new TreeNode(nums[left]);}int maxIdx=left;int maxValue=nums[left];for(int i=left+1;i<right;i++){if(nums[i]>maxValue){maxValue=nums[i];maxIdx=i;}}TreeNode node = new TreeNode(maxValue);node.left=traversal(nums, left, maxIdx);node.right=traversal(nums, maxIdx+1, 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(root1==null && root2!=null) return root2; if(root2==null && root1!=null) return root1; if (root1 == null && root2 == null) return null;TreeNode root=new TreeNode(root1.val+root2.val);root.left=mergeTrees(root1.left,root2.left);root.right=mergeTrees(root1.right, root2.right);return root;}
}
700.二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
例如,
因为本文的题设是二叉搜索树,所以这题就相对好办了,二叉搜索树是有序树:
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉搜索树
因此,找到值等于val的点然后递归返回从这个点以后的树即可:
class Solution {TreeNode traversal(TreeNode root, int val){if(root==null||root.val==val) return root;if(root.val>val){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, List<Integer> vec){if(root==null) return;traversal(root.left, vec);vec.add(root.val);traversal(root.right, vec);}public boolean isValidBST(TreeNode root) {List<Integer> res=new ArrayList<Integer>();traversal(root, res); // 将列表转换为数组Integer[] arr=res.toArray(new Integer[res.size()]); for(int i=1; i<arr.length;i++){if(arr[i]<=arr[i-1]) {return false; }}return true;}
}
这篇关于Leetcoder Day17| 二叉树 part06的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!