题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

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

inorder 保证为二叉树的中序遍历序列

解题方法

递归

前序数组的第一个元素及父节点元素，通过该元素可以先将中序数组进行分割，再对前序数组进行分割，重复该操作。若数组长度为0则返回NULL，若为1则返回父节点。利用哈希表节省中序数组中查找父节点的时间，传递数组的下标节省空间。
时间复杂度O(n)，空间复杂度O(n)
C++代码：

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
  map<int, int> in_map;
public:
  TreeNode* pre_in(const vector<int>& pre, const vector<int>& in, int pre_left, int pre_right, int in_left, int in_right) {
      if(pre_left>pre_right)  return NULL;
      int val = pre[pre_left];
      TreeNode* root = new TreeNode(val);

      int size = in_map[val] - in_left;
      root->left = pre_in(pre, in, pre_left+1, pre_left+size, in_left, in_left+size-1);
      root->right = pre_in(pre, in, pre_left+size+1, pre_right, in_left+size+1, in_right);

      return root;
  }

  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
      int n = inorder.size();
      for(int i=0; i<n; i++)  in_map[inorder[i]] = i;

      return pre_in(preorder, inorder, 0, n-1, 0, n-1);
  }
};

迭代法

对于前序数组中先后两个元素u,v，两者之间有两种可能：

v是u的左节点
v是u或其祖先节点的右节点

使用栈维护 当前未考虑过右孩子的节点。初始化in_i指向中序数组的第一个元素，若栈顶元素与中序遍历第in_i元素不相等时，将前序数组的下一个节点作为当前栈顶的左孩子压入栈；若相等则弹出栈顶并移动in_i直到不相等或栈空，此时将前序数组的下一个节点作为栈弹出元素的右孩子压入栈。
时间复杂度O(n)，空间复杂度O(n)
C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(!preorder.size())    return nullptr;
        stack<TreeNode*> nodes;
        TreeNode* root = new TreeNode(preorder[0]);
        nodes.push(root);
        for(int pre_i=1, in_i=0; pre_i<preorder.size(); pre_i++) {
            int val = preorder[pre_i];
            TreeNode* node = nodes.top();
            if(node->val != inorder[in_i]) {
                node->left = new TreeNode(val);
                nodes.push(node->left);
            }
            else {
                while(nodes.size() && nodes.top()->val==inorder[in_i]) {
                    node = nodes.top();
                    nodes.pop();
                    in_i++;
                }
                node->right = new TreeNode(val);
                nodes.push(node->right);
            }
        }

        return root;
    }
};

LeetCode

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

题目

解题方法

递归

迭代法