本文主要是介绍力扣labuladong——一刷day71,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、力扣1008. 前序遍历构造二叉搜索树
- 二、力扣108. 将有序数组转换为二叉搜索树
前言
二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「分解问题」的思维模式。
一、力扣1008. 前序遍历构造二叉搜索树
/*** 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 {Map<Integer,Integer> map = new HashMap<>();public TreeNode bstFromPreorder(int[] preorder) {int[] inorder = new int[preorder.length];System.arraycopy(preorder,0,inorder,0,preorder.length);Arrays.sort(inorder);for(int i = 0; i < inorder.length; i ++){map.put(inorder[i],i);}return fun(preorder,inorder,0,preorder.length-1,0,inorder.length-1);}public TreeNode fun(int[] preorder, int[] inorder, int proS, int proE, int inS, int inE){if(proS > proE || inS > inE){return null;}TreeNode cur = new TreeNode(preorder[proS]);int index = map.get(preorder[proS]);int len = index - inS;cur.left = fun(preorder,inorder,proS+1,proS+len,inS, index-1);cur.right = fun(preorder,inorder,proS+len+1,proE,index+1,inE);return cur;}
}
二、力扣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 fun(nums,0,nums.length-1);}public TreeNode fun(int[] nums, int low, int high){if(low > high){return null;}int mid = (high+low)/2;TreeNode cur = new TreeNode(nums[mid]);cur.left = fun(nums,low,mid-1);cur.right = fun(nums,mid+1,high);return cur;}
}
这篇关于力扣labuladong——一刷day71的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!