根据前序遍历结果构造二叉搜索树

根据前序遍历结果构造二叉搜索树-力扣 1008 题

题目说明：

1.preorder 长度>=1

2.preorder 没有重复值

直接插入

解题思路：

数组索引[0]的位置为根节点，与根节点开始比较，比根节点小的就往左边插，比根节点大的就往右边插，插入的前提是要插入的位置是Null

注意：根据前序遍历的结果，可以唯一地构造出一个二叉搜索树

对于前序遍历不是太理解的，作者推荐适合小白的文章：

二叉树的初步认识_加瓦不加班的博客-CSDN博客

// 8 5 1 7 10 
/*
                8
               / \
              5   10
             / \   \
            1   7  12
         */

// 8 5 1 7 10 
/*8/ \5   10/ \   \1   7  12*/
public TreeNode bstFromPreorder(int[] preorder) {//数组索引[0]的位置为根节点TreeNode root = insert(null, preorder[0]);for (int i = 1; i < preorder.length; i++) {insert(root, preorder[i]);}return root;
}private TreeNode insert(TreeNode node, int val) {//找到空位了就创建一个新节点将val插入进去if (node == null) {return new TreeNode(val);}if(val < node.val) {//继续查询空位 如果查询到空位，要和父节点建立关系node.left = insert(node.left, val);} else if(node.val < val){node.right = insert(node.right, val);}return node;
}

上限法

解题思路：

//依次处理prevorder中每个值，返回创建好的节点或者null
//1.如果超过上限，返回null 作为孩子返回
//2.如果没超过上限，创建节点，并设置其左右孩子
//  左右孩子完整后返回

//依次处理prevorder中每个值，返回创建好的节点或者null
//1.如果超过上限，返回null 作为孩子返回
//2.如果没超过上限，创建节点，并设置其左右孩子
//  左右孩子完整后返回
public TreeNode bstFromPreorder(int[] preorder) {return insert(preorder, Integer.MAX_VALUE);
}int i = 0;
private TreeNode insert(int[] preorder, int max) {//递归结束条件if (i == preorder.length) {return null;}int val = preorder[i];System.out.println(val + String.format("[%d]", max));if (val > max) {//如果超过上限，返回null 作为孩子返回return null;}//如果没超过上限，创建节点，并设置其左右孩子TreeNode node = new TreeNode(val);i++;node.left = insert(preorder, node.val); node.right = insert(preorder, max);     return node;
}

依次处理 prevorder 中每个值, 返回创建好的节点或 null 作为上个节点的孩子

1. 如果超过上限, 返回 null

2. 如果没超过上限, 创建节点, 并将其左右孩子设置完整后返回

   • i++ 需要放在设置左右孩子之前，意思是从剩下的元素中挑选左右孩子

分治法

解题思路：

//分治法 8,5,1,7,10,12
//8根  左：5,1,7   右：10,12
//5根  左：1     右：7
//10根 左：null  右：12

//我们如何去分治呢？首先我们找到的是 题目给出的是前序遍历出来的，那么我们只要找到比根节点大的数开始就可以区分左、右子树的范围

//分治法 8,5,1,7,10,12
//8根  左：5,1,7   右：10,12
//5根  左：1     右：7
//10根 左：null  右：12//我们如何去分治呢？首先我们找到的是 题目给出的是前序遍历出来的，那么我们只要找到比根节点大的数开始就可以区分左、右子树的范围
public TreeNode bstFromPreorder(int[] preorder) {return partition(preorder, 0, preorder.length - 1);
}
//int start, int end 告诉处理范围
private TreeNode partition(int[] preorder, int start, int end) {//结束条件if (start > end) {return null;}//获取根节点  创建根节点对象TreeNode root = new TreeNode(preorder[start]);//跳过根节点开始找左、右子树的范围int index = start + 1;//条件是一直找到区域的结束while (index <= end) {//区分左、右子树的范围if (preorder[index] > preorder[start]) {break;}index++;}//此时 index 就是左、右子树的分界线root.left = partition(preorder, start + 1, index - 1);root.right = partition(preorder, index, end);return root;
}

• 刚开始 8, 5, 1, 7, 10, 12，方法每次执行，确定本次的根节点和左右子树的分界线

• 第一次确定根节点为 8，左子树 5, 1, 7，右子树 10, 12

• 对 5, 1, 7 做递归操作，确定根节点是 5， 左子树是 1， 右子树是 7

• 对 1 做递归操作，确定根节点是 1，左右子树为 null

• 对 7 做递归操作，确定根节点是 7，左右子树为 null

• 对 10, 12 做递归操作，确定根节点是 10，左子树为 null，右子树为 12

• 对 12 做递归操作，确定根节点是 12，左右子树为 null

• 递归结束，返回本范围内的根节点