数据结构与算法之从前序与中序遍历序列构造二叉树

• 问题提出：leetcode原题
• • 思路分析
  • • 思路总结：
  • 代码示例

通过前序遍历+中序遍历来构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

视频讲解：这里引用leetcode官方简介视频

[从前序与中序遍历序列构造二叉树 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）.ts](assets/从前序与中序遍历序列构造二叉树 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）-20220602150410-cot75wo.ts)

1. 第一步：根据前序遍历A B D E G C F H确定头结点是A，根据中序遍历D B G E A C H F将树划分为左子树D B G E和右子树 C H F。
2. 划分为左右两棵子树：对于左子树，前序遍历是 B D E G，后续遍历是 D B G E。对于右子树，前序遍历是 C F H，后续遍历是 C H F。
3. 对左子树和右子树分别运用第一步和第二步进行分析。
4. 递归结束的条件：当中序遍历的节点只剩下一个节点的时候，那么这个节点就是叶子节点。

package tree;

import java.util.LinkedHashMap;


public class BuildTreeByMidAndPre {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        if (preLen != inLen) {
            return null;
        }
        LinkedHashMap map = new LinkedHashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return help(preorder, 0, preLen - 1, map, 0, inLen - 1);
    }

    
    private TreeNode help(int[] preorder, int preLeft, int preRight, LinkedHashMap map, int inLeft, int inRight) {
        //递归结束条件
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        //创建根节点
        int rootVal = preorder[preLeft - 1];
        TreeNode rootNode = new TreeNode(rootVal);
        //根节点在中序遍历序列的位置
        int pIndex = map.get(rootVal);
        rootNode.left = help(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);
        rootNode.right = help(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);
        return rootNode;
    }

}