中序和后序遍历构建二叉树[递归划分区间与回溯拼接子树+中后序和中前序的相似与不同]

前言

根据一个序列，可以通过递归划分区间，回溯拼接子树来完成树生成。
前中序遍历，一个能确定根节点，一个能拿着根节点划分左右区间，抽象的完成了前置任务，所以前中序能够确定一颗二叉搜索树。同理，中后序亦是如此，不过后序遍历根节点在后，而且遍历为左右根，所以根过了就是右，所以需要先构建右子树，再构建左子树。

一、中序和后序遍历构建二叉搜索树

二、自上而下+自下而上

// 根据中序 + 后序来构建二叉树。
class BuildTree2 {
    
    /* target：用后序和中序遍历来构建二叉树。 后序作用？从右到左依次得到左子树上的所有根节点。 中序作用？靠着后序遍历的根节点划分左右子树，不断划分，从下到上生成二叉树。 */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    
        // assert 无重复元素。
        Map<Integer, Integer> m = new HashMap<>();
        // 准备工作，快速得到根节点位置，进行左右子树划分。
        for (int i = 0; i < inorder.length; i++) m.put(inorder[i], i);
        // 构建树
        idx = postorder.length - 1;
        return buildTree(inorder, postorder, 0, inorder.length - 1, m);
    }

    int idx = 0;

    private TreeNode buildTree(int[] inorder, int[] postorder, int begin, int end, Map<Integer, Integer> m) {
    
        if (begin > end) return null;
        // 用根节点来划分左右子树，根节点由preorder[idx]得来。
        int mid = m.get(postorder[idx--]);
        // 得到递归生成好的左右孩子。
        // 注意，后续遍历是左右根，所以先得到右子树，再得左子树，这是和前序遍历定位的区别。
        TreeNode right = buildTree(inorder, postorder, mid + 1, end, m);
        TreeNode left = buildTree(inorder, postorder, begin, mid - 1, m);
        // 生成根节点。
        TreeNode root = new TreeNode(inorder[mid]);
        // 拼接上左右子树。
        root.left = left;
        root.right = right;
        // 返回拼接好的root树。
        return root;
    }

    // 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;
        }
    }

}

总结

1）生成树基础，自上而下递归划分区间，自下而上回溯拼接左右子树。
2）前中序遍历生成树与中后序生成树的相似与不同。

参考文献

[1] LeetCode 中序和后续遍历构建二叉树
[2] 中序和前序遍历构建二叉树