12._从前序与中序遍历序列构造二叉树

• 2.12

  • inorder 放入 map 做索引，仅做 left 和 right 的更新使用
  • 用for 找也行，但时间复杂度不行

• 1.30

  • 结束条件 left>rigth，等于是符合的

• 1.29

  • 就是左右边界做，而不是全局游标，inorder 是根据 map 来取的

• 1.17

  • 做了好多次，有点难，与7.有序列表转换二叉搜索树一起记忆，边界是由 中序遍历的 map 决定的
  • ~~map 的 key 和 val 应该分辨清，cur 为全局的

• 11.12

  • 想到了map思路,递归思路没想清
  • 需要把map声明在外面,因为build在外面递归
  • 把先序遍
  • 历的索引声明全局,然后递归每取一个++
  • 递归build左右子树(靠inorder索引一分为二)

class Solution {
    Map<Integer,Integer> inorderMap;
    int preorderIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderMap = new HashMap<>();
        //预处理L记录中序中每个值的位置
        for(int i =0;i<inorder.length;i++){
            inorderMap.put(inorder[i],i);
        }
        return build(preorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder,int left,int right){
        if(left>right) return null;
        //当前根节点
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        //根据map划分左右子树
        int inorderIndex = inorderMap.get(rootVal);
        //递归构造左右子树
        root.left = build(preorder,left,inorderIndex-1);
        root.right = build(preorder,inorderIndex+1,right);
        return root;
    }
}

• 用map存储中序的序号
• 声明全局变量map和先序遍历索引
• 根据索引创建跟节点(记得++),递归构造左右子树

以下是错的⬇️

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root =new TreeNode(preorder[0]);
        biuld(root,preorder,inorder,1);
        return root;
    }
    public void biuld(TreeNode root,int[] preorder,int[] inorder,int cur){
        
        TreeNode node = new TreeNode(preorder[cur]);
        cur++;
        int lotation=0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==preorder[cur]){
                lotation=i;
            }
        }
        node.left = new TreeNode(inorder[lotation-1]);
        node.right = new TreeNode(inorder[lotation+1]);
        biuld(node.left,preorder,inorder,cur);
        biuld(node.right,preorder,inorder,cur);
    }

}