西安网站seo外包,个人开发者,百度如何免费打广告,网络营销渠道有哪三类由于这两道题思路极其类似#xff0c;在此统一记录#xff1a;
108题.将有序数组转换为平衡二叉搜索树 思路#xff1a;给定的数组已经升序排列#xff0c;而二叉搜索树中序遍历的结果就是升序#xff0c;但是仅凭中序遍历不能确定一颗二叉树#xff0c;但是题目只是说…由于这两道题思路极其类似在此统一记录
108题.将有序数组转换为平衡二叉搜索树 思路给定的数组已经升序排列而二叉搜索树中序遍历的结果就是升序但是仅凭中序遍历不能确定一颗二叉树但是题目只是说将升序序列转换为平衡二叉搜索树且答案不唯一所以不要求确定如何平衡呢我们尽量保证左右子树一样多的节点不就可以吗那么我们就能通过每次取数组最中间的元素作为二叉树节点最终就能构建整个平衡二叉搜索树。
/*** 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 Solution {public TreeNode sortedArrayToBST(int[] nums) {return dfs(nums,0,nums.length-1);}public TreeNode dfs(int[] nums, int lo, int hi){if(lo hi) {return null;}int mid lo (hi - lo) / 2;//计算中间节点TreeNode root new TreeNode(nums[mid]);root.left dfs(nums,lo,mid - 1);//在数组左半边构建左子树root.right dfs(nums,mid 1,hi);//在数组右半边构建右子树return root;}}接下来看1382题解法基本一样不过多了一个步骤而已 1382.将二叉搜索树变平衡 思路这里我们是有了一颗二叉搜索树将树变平衡我们有了二叉搜索树那么就有了升序序列有了升序序列不就跟108题一样了吗将有序数组转换为平衡二叉搜索树。获取升序序列就使用中序遍历记录即可后面的操作就是使用升序序列构建二叉平衡树了。
/*** 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 Solution {public TreeNode balanceBST(TreeNode root) {ArrayListInteger nums new ArrayList();dfs(root,nums);//中序遍历获取升序序列return BSTDFS(nums,0,nums.size()-1);//使用升序序列构建平衡二叉搜索树}public void dfs(TreeNode root,ArrayListInteger nums){if(root null) {return;}dfs(root.left,nums);nums.add(root.val);dfs(root.right,nums);}public TreeNode BSTDFS(ArrayListInteger nums,int lo,int hi) {if(lo hi) {return null;}int mid lo (hi - lo) / 2;TreeNode root new TreeNode(nums.get(mid));root.left BSTDFS(nums, lo,mid- 1);root.right BSTDFS(nums,mid1,hi);return root;}
}总结解这两道题的关键在于要知道二叉搜索树的中序遍历是有序的
