105. 从前序与中序遍历序列构造二叉树（中等）

素颜马尾好姑娘i 2022-09-10 05:23 103阅读 0赞

Leetcode链接：[105. 从前序与中序遍历序列构造二叉树][105.]

### 题目描述 ###

> 给定一棵树的前序遍历 `preorder` 与中序遍历 `inorder`。请构造二叉树并返回其根节点。

示例 1:  
![在这里插入图片描述][45345cbbd7f648b8ae63f8c4ecf1eb3c.png]

> Input: preorder = \[3,9,20,15,7\], inorder = \[9,3,15,20,7\]  
> Output: \[3,9,20,null,null,15,7\]

示例 2:

> Input: preorder = \[-1\], inorder = \[-1\]  
> Output: \[-1\]

提示:

> 1 <= preorder.length <= 3000  
> inorder.length == preorder.length  
> \-3000 <= preorder\[i\], inorder\[i\] <= 3000  
> preorder 和 inorder 均`无重复元素`  
> inorder 均出现在 preorder  
> preorder 保证为二叉树的前序遍历序列  
> inorder 保证为二叉树的中序遍历序列

### 源码 ###

思想：

*  主要利用二叉树前序和中序遍历的定义，计算各自左右子树所在数组区间
 *  为了方便查找前序节点在中序的位置，首先使用Map存储中序的索引

/**
     * 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;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            int n = preorder.length;
            int m = inorder.length;
            if(n != m) return null;
    		//存储中序节点的数值所对应的index
            HashMap<Integer,Integer> inorder_map = new HashMap<>();
            for(int i = 0; i < m; i++){
        
                inorder_map.put(inorder[i],i);
            }
            return buildTree(preorder, 0, n - 1,inorder_map, 0, m - 1);
        }
    
        public TreeNode buildTree(int[] preorder, int preLeft, int preRight, 
                                    HashMap<Integer,Integer> map, int inLeft, int inRight){
        
            if(preLeft > preRight || inLeft > inRight) return null;
            TreeNode node = new TreeNode(preorder[preLeft]);
            int pIndex = map.get(preorder[preLeft]);
            node.left = buildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);
            node.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);
            return node;
        }
    }

计算下标：

`pIndex = map.get(preorder[preLeft])`  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

[105.]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[45345cbbd7f648b8ae63f8c4ecf1eb3c.png]: /images/20220829/dfc755a3ed0d4743803e2fee992e4ef1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/a036486e9544464f81be0d0fff1a3e21.png