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

前言

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

一、根据前序&中序遍历生成二叉树

二、递归划分+回溯拼接子树

package everyday.medium;

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

// 用前序和中序遍历来构建二叉树。
public class BuildTree {
    
    /* target：用前序和中序遍历来构建二叉树。 前序作用？依次得到左子树上的所有根节点。 中序作用？靠着前序遍历的根节点划分左右子树，不断划分，从下到上生成二叉树。 */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        // assert 无重复元素。
        Map<Integer, Integer> 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<Integer, Integer> 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 根据前序&中序遍历生成二叉树