题目内容

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

示例

示例 1:

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、1 <= preorder.length <= 3000
2、inorder.length == preorder.length
3、-3000 <= preorder[i], inorder[i] <= 3000
4、preorder 和 inorder 均无重复元素
5、inorder 均出现在 preorder
6、preorder 保证为二叉树的前序遍历序列
7、inorder 保证为二叉树的中序遍历序列

题解

本题是一道经典的题目，可以采用递归的方式构建整棵二叉树，先递归创建左子树和右子树，然后再创建根节点，最后让根节点指向左右两颗子树即可。

具体地，有如下的步骤：

1、首先，前序遍历的第一个点一定是根节点

2、在中序遍历中找到根节点的位置i，则i左边的部分是左子树的中序遍历，i右边的部分是右子树的中序遍历

3、若左子树的中序遍历找到根节点的位置j，则在前序遍历中，根节点右边的j个数就是左子树的前序遍历，剩下的部分就是右子树的前序遍历

4、有了左右两颗子树的前中序遍历，就可以递归创建出二叉树的左右子树，最后让根节点指向两颗子树即可。

找某个元素的位置，建议使用hash表或者一个数组也可。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();//数的节点个数
        for (int i = 0; i < n; i ++ )
            pos[inorder[i]] = i;//创建一个数组，用于定位中序遍历中各节点位置
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }
		
  	//pre为前序遍历的数组，in为中序遍历的数组，pl和pr为前序遍历中需要处理的左右两边的范围，il和ir为中序遍历中需要处理的左右两边的范围。
    TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir)
    {
        if (pl > pr) return NULL;//如果左边范围大于右边范围，说明不存在子树，返回NULL
        int k = pos[pre[pl]] - il;//找到了根节点的位置
        TreeNode* root = new TreeNode(pre[pl]);//递归创建每个部分子树的根节点
        root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);//创建左子树
        root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);//创建右子树
        return root;//返回根节点
    }
};