题目链接

题目描述

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解题思路

方法一（递归分治）

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。

以题目示例为例：

前序遍历划分 [ 3 | 9 | 20 15 7 ]
中序遍历划分 [ 9 | 3 | 15 20 7 ]
根据以上性质，可得出以下推论：

前序遍历的首元素为树的根节点 node 的值。
在中序遍历中搜索根节点 node 的索引，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ] 。
根据中序遍历中的左 / 右子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ] 。
7. 重建二叉树* - 图2
分治算法解析：

递推参数：根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right ；
终止条件：当 left > right ，代表已经越过叶节点，此时返回 nullnull ；
递推工作：

1.建立根节点 node ：节点值为 preorder[root] ；
2.划分左右子树：查找根节点在中序遍历 inorder 中的索引 i ；
为了提升效率，本文使用哈希表 dic 存储中序遍历的值与索引的映射，查找操作的时间复杂度为 O(1)
3.构建左右子树：开启左右子树递归；

   根节点索引    中序遍历左边界    中序遍历右边界<br />左子树     root + 1                    left                            i - 1<br />右子树 i - left + root + 1    i + 1                     right<br />i - left + root + 1含义为 根节点索引 + 左子树长度 + 1（就是经过根节点和左子树后的第一个结点是右子树的根节点）<br />i-left是左子树长度

返回值：回溯返回 node ，作为上一层递归中根节点的左 / 右子节点；

/**
* 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:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
      pre = preorder;
      for(int i = 0; i < inorder.size(); i++)
          dic[inorder[i]] = i;
      return recur(0, 0, inorder.size() - 1);
  }
private:
  vector<int> pre;
  unordered_map<int, int> dic;
  // root为前序遍历顺序里的下标，left和right为中序遍历顺序的下标
  // 先根据先序遍历根结点将后续遍历分为左子树和右子树
  // 再遍历求左右子树
  TreeNode* recur(int root, int left, int right){
      if(left > right) return nullptr;
      TreeNode* node = new TreeNode(pre[root]);
      int i = dic[pre[root]];
      // root是pre中的位置,左右边界是inorder的位置
      node->left = recur(root + 1, left, i - 1);
      node->right = recur(root + i - left + 1, i + 1, right);
      return node;
  }
};

时间复杂度 O(N) ：其中 N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间。最差情况下，树退化为链表，递归深度达到 N ，占用 O(N) 额外空间；最好情况下，树为满二叉树，递归深度为 logN ，占用 O(logN) 额外空间。
方法二（非递归）
Image.png ```cpp /**

Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}

}; / class Solution { public: TreeNode reConstructBinaryTree(vector pre,vector vin) {

  int vinlen = vin.size();
  if(vinlen==0)
      return NULL;
  vector<int> pre_left,vin_left,pre_right,vin_right;

  TreeNode* head = new TreeNode(pre[0]);

  int gen =0;
  for(int i=0;i<vinlen;i++)
      if(vin[i]==pre[0])
      {
          gen=i;
          break;
      }
  for(int i=0;i<gen;i++)
  {
      vin_left.push_back(vin[i]);
      pre_left.push_back(pre[i+1]);
  }
  for(int i=gen+1;i<vinlen;i++)
  {
      vin_right.push_back(vin[i]);
      pre_right.push_back(pre[i]);
  }
  head->left=reConstructBinaryTree(pre_left, vin_left);
  head->right=reConstructBinaryTree(pre_right, vin_right);
  return head;

} }; ```

7. 重建二叉树*

题目链接

题目描述

解题思路

方法一（递归分治）

方法二（非递归）