07.重建二叉树 (Medium)*

题目描述*

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

示例*

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

限制*

0 <= 结点个数 <= 5000

代码*

先复习一下树的结构：

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

根据前序遍历和中序遍历的结果划分，根据前序的第一个结点把中序分为该结点的左右子树中序遍历结果，递归或用辅助栈求解。

经典的递归建树，重点在于控制遍历序列的边界。¹

从先序遍历获取根结点值 preorder[rootPos]，创建根结点，然后其在获取中序遍历的位置 pos，构建左子树，左子树的根结点值为 preorder[rootPos + 1]，对应的中序遍历序列的范围为 [start, pos - 1]，左子树结点数为 pos - start，由此计算右子树的根结点值为 preorder[rootPos + pos - start + 1]，对应中序遍历序列范围为 [pos + 1,end]，由此递归。

可以使用 map 优化每次查找中序遍历位置的过程，效果很显著。

class Solution {
public:
    TreeNode* build(vector<int>& preorder, int rootPos,
                    vector<int>& inorder, int start, int end, unordered_map<int, int>& posMap) {
        if(start > end) {
            return nullptr;
        }
        TreeNode *root = new TreeNode(preorder[rootPos]);
        // 找到根结点在 inorder 中的位置
        int pos = posMap[preorder[rootPos]];
        // 构造左子树，根结点在 preorder 中的位置时 rootPos + 1，inorder 的范围时 [start, pos - 1]
        root->left = build(preorder, rootPos + 1, inorder, start, pos - 1, posMap);
        // 构造右子树
        root->right = build(preorder, rootPos + 1 + pos - start, inorder, pos + 1, end, posMap);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) {
            return nullptr;
        }
        unordered_map<int, int> posMap;
        for(int i = 0; i < inorder.size(); i++) {
            posMap[inorder[i]] = i;
        }
        return build(preorder, 0, inorder, 0, inorder.size() - 1, posMap);
    }
};

非递归算法，使用栈。当我们只有先序遍历序列还原树时，将根结点压栈后，需要考虑下一个是左还是右，这可以通过中序遍历确定。

以 preorder = [3, 9, 20, 15, 7 ], inorder = [ 20, 9, 15, 3, 7 ] 举例，先将 3 压栈，然后判断 9 是左还是右。此时检查中序，第一个是 20，这表明 9 一定是 3 的左孩子（如果是右那么表示左子树为空，则中序第一个应该是 3）。接下来的 20 同理，目前构造出的树为：

同时先序遍历的 20 与中序遍历 20 相等了，这说明中序遍历的 15 不是左，根据中序遍历判断 15 是谁的右孩子：

如果是 3 的右子树，对应的中序遍历为 20, 9, 3, 15
如果是 9 的右子树，对应的中序遍历为 20, 9, 15
如果是 20 的右子树，对应的中序遍历为 20, 15

与给定的中序遍历比较，匹配的是 20, 9, 15，即 15 就是最后相等的结点的右孩子。

综上，我们用栈保存遍历过的结点，遍历前序序列，一直作为当前根结点的左子树，知道当前结点和中序遍历结点相等，那么我们比较正序的中序和倒序的前序，找到最后一个相等的位置，把它作为该结点的右子树。

脑子 8 太行，这种方法还没怎么理解。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }
    Stack<TreeNode> roots = new Stack<TreeNode>();
    int pre = 0;
    int in = 0;
    //先序遍历第一个值作为根结点
    TreeNode curRoot = new TreeNode(preorder[pre]);
    TreeNode root = curRoot;
    roots.push(curRoot);
    pre++;
    //遍历前序遍历的数组
    while (pre < preorder.length) {
        //出现了当前结点的值和中序遍历数组的值相等，寻找是谁的右子树
        if (curRoot.val == inorder[in]) {
            //每次进行出栈，实现倒着遍历
            while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
                curRoot = roots.peek();
                roots.pop();
                in++;
            }
            //设为当前的右孩子
            curRoot.right = new TreeNode(preorder[pre]);
            //更新 curRoot
            curRoot = curRoot.right;
            roots.push(curRoot);
            pre++;
        } else {
            //否则的话就一直作为左子树
            curRoot.left = new TreeNode(preorder[pre]);
            curRoot = curRoot.left;
            roots.push(curRoot);
            pre++;
        }
    }
    return root;
}

迭代

/**
 * 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) {
        if(preorder.size() == 0) {
            return nullptr;
        }
        int rootPos = 0;
        int inPos = 0
        TreeNode *root = new TreeNode(preorder[rootPos++]);
        stack<TreeNode*> s;
        s.push(root);
        while(rootPos < preorder.size()) {
            TreeNode *tmp = nullptr;
            // 当栈顶元素是 inPos 位置的中序节点，表明已经构建到当前位置。
            // 未进入循环，tmp == nullptr 表示左子树已构建完毕。
            while(!s.empty() && s.top()->val == inorder[inPos]) {
                inPos++;
                tmp = s.top();
                s.pop();
            }
            TreeNode *cur = new TreeNode(preorder[rootPos]);
            if(tmp == nullptr) {
                s.top()->left = cur;
            }else {
                tmp->right = cur;
            }
            s.push(cur);
            rootPos++;
        }
        return root;
    }
};

脑子实属 8 太行，一定要多熟悉熟悉。 ↩

最后更新: July 23, 2022