先序和中序构造二叉树

code_105

• tips : 先序，后序不能确定二叉树。

思路

先序 ： 根--左--右
中序：左--根--右
在先序中找根分割中序为左右子树，再去找左右子树的跟再分割，可以递归实现。

实现

• 建树函数返回所见树的根节点，所需参数：先序数组，中序数组，两个数组的left,right索引。
• HashMap存储中序的值和对应索引，方便分割中序数组。
• preLeft =
• 左子树的inRight = HashMap.get(preOrder[preLeft]) - 1
• 左子树的inLeft = 0
• 左子树的preLeft = preLeft + 1
• 左子树的PreRight = HashMap.get(preOrder[preLeft])
• 右子树 inLeft = HashMap.get(preOrder[preLeft]) + 1
• 右子树的inRight = n - 1
• 右子树的preLeft = HashMap.get(preOrder[preLeft]) + 1
• 右子树的PreRight = n - 1

HashMap<Integer, Integer> hashMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        hashMap = new HashMap<>();
        for (int i = 0; i < preorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] preorder,
    int[] inorder, int leftPreorder,
    int rightPreorder, int leftInorder, int rightInorder) {
        if (leftPreorder > rightPreorder) {
            return null;
        }
        int preOrderRoot = leftPreorder;
        int inOrderRoot = hashMap.get(preorder[preOrderRoot]);
        TreeNode node = new TreeNode(preorder[preOrderRoot]);
        
        int leftTreeSize = inOrderRoot - leftInorder;
        
        node.left = myBuildTree(preorder, inorder, 
        leftPreorder + 1,
        leftPreorder + leftTreeSize, 
        leftInorder,
        inOrderRoot - 1);

        node.right = myBuildTree(preorder, inorder,
        leftPreorder + leftTreeSize + 1,
        rightPreorder, 
        inOrderRoot + 1, 
        rightInorder);
        
        return node;
    }