AcWing.18 重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

• 二叉树中每个节点的值都互不相同；
• 输入的前序遍历和中序遍历一定合法；

数据范围

树中节点数量范围 $[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

Code

   
  /**
* 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;  // 定义一个哈希数组，用于快速查找前序遍历第一个节点在中序遍历中的位置。
	   // 目的：使得运行效率更快，因为此操作是O(1)的复杂度
	   vector<int> preorder, inorder;  // 将前序遍历，中序遍历数组定义为全局变量，方便写代码。

	   //pl: preorder_left, pr:preorder_right, il: inorder_left, ir: inoder_right
	   TreeNode* build(int pl, int pr, int il, int ir) {

		   // 如果前序遍历的区间小于1就退出
		   if(pl > pr) return NULL;  // 递归结束的条件。

		   TreeNode* root = new TreeNode(preorder[pl]);  // 创建一个节点，前序遍历的第一个节点也就是当前的根节点

		   int k = pos[preorder[pl]];  // 用哈希查找该点在中序遍历中的位置
		   // k就是根节点在中序遍历中的位置


		   // 创建子树时候，build函数递归时，边界情况
		   // 模拟一下知道前序、中序遍历的树，求二叉树
		   // 当找到根节点的时候，也就是前序遍历的第一个数，
		   // 此时需要查找它在中序遍历中的位置k，
		   // 在k的左边的数都是它的左子树，在k的右边的数都是它的右子树
		   // 递归处理左右两边
		   // build(int pl, int pr, int il, int ir)里面的参数要符合一下情况
		   // 处理左子树
		   // 1. 由于前序遍历第一个节点已经用过，故起点为pl + 1
		   // 2. 而在左子树中前序遍历的长度，取决于中序遍历中k的左右有多少个数
		   // 3. 一共有k - il - 1个数，不算上k本身，终点为pl + 1 + k - il - 1
		   // 4. 中序遍历起点为il
		   // 5. 中序遍历的终点为k - 1，不算k本身

		   // 处理右子树
		   // 1. 右子树前序遍历的起点应该是左子树前序遍历的终点加1
		   //     pl + 1 + k - il - 1 + 1
		   // 2. 而在右子树中前序遍历的终点当然为pr
		   // 3. 中序遍历起点为k + 1，不算k本身
		   // 4. 中序遍历的终点为ir

		   // 递归创建左子树
		   // 记住不要算k这个节点，因为已经作为了根节点
		   root->left = build(pl + 1, pl + 1 + k - il - 1, il, k - 1);

		   // 递归创建右子树
		   root->right = build(pl + 1 + k - il - 1 + 1, pr, k + 1, ir);

		   // 返回创建的树
		   return root;
	   }

	   TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
		   // 赋值
		   preorder = _preorder, inorder = _inorder;
		   // 预处理哈希
		   int n = inorder.size();  // 计算中序遍历长度。
		   for(int i = 0; i < n; i ++ ) pos[inorder[i]] = i;

		   // 返回递归函数。
		   return build(0, n - 1, 0, n - 1);  // 前序遍历起点，终点；中序遍历起点，终点。
	   }
  };