题目描述
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
- 二叉树中每个节点的值都互不相同；
- 输入的前序遍历和中序遍历一定合法；
数据范围
树中节点数量范围 [0,100]。
样例
给定： 前序遍历是：[3, 9, 20, 15, 7] 中序遍历是：[9, 3, 15, 20, 7] 返回：[3, 9, 20, null, null, 15, 7, null, null, null, null] 返回的二叉树如下所示： 3 / \ 9 20 / \ 15 7
方法一：递归 O(n)
我们可以递归构建二叉树，具体步骤如下：
第一步： 初始化，将每个元素在中序遍历数组中的下标位置用哈希表 pos 存起来，方便后续计算。
第二步： 传入递归参数，开始递归创建二叉树，参数包含 pl 和 pr 即当前遍历的树在前序遍历数组中的左边界和右边界，il 和 ir 即当前遍历的树在中序遍历数组中的左边界和右边界。
第三步： 进行递归操作，具体步骤如下：
找到前序遍历的第一个数即根结点，创建结点。
通过第一步找到的根结点在中序遍历数组中找到它的位置，由于之前已经用哈希表保存过了，所以直接计算根结点左子树结点个数 k = pos[preorder[pl]] - il 。
继续递归构建其左子树与右子树。
/** * 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 = inorder.size(); //记录每个值在中序数组中的下标位置 for (int i = 0; i < n; i++) pos[inorder[i]] = i; return dfs(preorder, inorder, 0, n - 1, 0, n - 1); } TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) { if (pl > pr) return NULL; TreeNode* root = new TreeNode(preorder[pl]); int k = pos[preorder[pl]] - il; //获取左子树的结点个数 root->left = dfs(preorder, inorder, pl + 1, pl + k, il, il + k - 1); root->right = dfs(preorder, inorder, pl + 1 + k, pr, il + k + 1, ir); return root; } };
欢迎大家在评论区交流~
