根据前序&中序遍历生成二叉树[左子树|根|右子树的划分/生成/拼接问题]

• 前言
• 一、根据前序&中序遍历生成二叉树
• 二、递归划分+回溯拼接子树
• 总结
• 参考文献

二叉树的生成，一般来说是从上往下分析即划分，从下往上拼接子树，最终得到整个二叉树。考察左右子树划分 + 左右子树回溯拼接知识点。

package everyday.medium;

import java.util.HashMap;
import java.util.Map;

// 用前序和中序遍历来构建二叉树。
public class BuildTree {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // assert 无重复元素。
        Map m = new HashMap<>();
        // 准备工作，快速得到根节点位置，进行左右子树划分。
        for (int i = 0; i < inorder.length; i++) m.put(inorder[i], i);
        // 构建树
        return buildTree(preorder, inorder, 0, inorder.length - 1, m);
    }

    int idx = 0;

    private TreeNode buildTree(int[] preorder, int[] inorder, int begin, int end, Map m) {
        if (begin > end) return null;
        // 用根节点来划分左右子树，根节点由preorder[idx]得来。
        int mid = m.get(preorder[idx++]);
        // 得到递归生成好的左右孩子。
        TreeNode left = buildTree(preorder, inorder, begin, mid - 1, m);
        TreeNode right = buildTree(preorder, inorder, mid + 1, end, 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 根据前序&中序遍历生成二叉树