「LeetCode」从前序与中序遍历序列构造二叉树

2020-04-21
摘要: 本文讨论了如何从前序和中序遍历结果中重构二叉树。

问题描述#

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
假设树中没有重复的元素。

例如,给出

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

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

思路#

思路比较直观,对于 preorder 来说,第一个元素就是 root。此时我们再去寻找 rootinorder 中的位置,例如,对于上述例子来说,root = 3, rootIndex = 1。于是就得到: inorder 中,在 rootIndex 左侧的元素都在左子树中,在 rootIndex 右侧的元素都在右子树中。而且此时我们可以知道,左子树的大小为 $1$,右子树的大小为 $3$。于是我们可以把两个数组分为三个部分:root, left-treeright-tree,我们再针对 left-treeright-tree 重复这个过程,便得到了整棵树的信息。

$$\underline{3},\underline{9},\underline{20,15,7}$$

$$\underline{9},\underline{3},\underline{15,20,7}$$

例题#

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

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

class Solution {
public:
    unordered_map<int, int> m;
    
    TreeNode* recursiveBuild(vector<int>& preorder, int i, int j, vector<int>& inorder, int p, int q) {
        if(i > j || p > q) return NULL;
        int root = preorder[i];
//        int rootIndex = int(find(inorder.begin(), inorder.end(), root) - inorder.begin());
        int rootIndex = m[root];
        int leftTreeCount = rootIndex - p, rightTreeCount = q - rootIndex;

        TreeNode* node = new TreeNode(root);
        node->left = recursiveBuild(preorder, i+1, i+leftTreeCount, inorder, p, p+leftTreeCount-1);
        node->right = recursiveBuild(preorder, j-rightTreeCount+1, j, inorder, q-rightTreeCount+1, q);
        return node;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // for faster searching purpose
        for(int i = 0; i < inorder.size(); ++i) {
            m[inorder[i]] = i;
        }
        
        return recursiveBuild(preorder, 0, int(preorder.size() - 1), inorder, 0, int(inorder.size() - 1));
    }
};

106. 从中序与后序遍历序列构造二叉树#

106. 从中序与后序遍历序列构造二叉树

给定后序遍历结果来构造二叉树,唯一的区别是后序遍历结果的组成为:

$$[\mathrm{left-tree, right-tree, root}]$$

所以只需要更改一下取的下标即可。

class Solution {
public:
    unordered_map<int, int> m;
    TreeNode* recursiveBuild(vector<int>& postorder, int i, int j, vector<int>& inorder, int p, int q) {
        if(i > j || p > q) return NULL;
        int root = postorder[j];
        //        int rootIndex = int(find(inorder.begin(), inorder.end(), root) - inorder.begin());
        int rootIndex = m[root];
        int leftTreeCount = rootIndex - p, rightTreeCount = q - rootIndex;
        
        TreeNode* node = new TreeNode(root);
        node->left = recursiveBuild(postorder, i, i+leftTreeCount-1, inorder, p, p+leftTreeCount-1);
        node->right = recursiveBuild(postorder, j-rightTreeCount, j-1, inorder, q-rightTreeCount+1, q);
        return node;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i = 0; i < inorder.size(); ++i) {
            m[inorder[i]] = i;
        }
        
        return recursiveBuild(postorder, 0, int(postorder.size() - 1), inorder, 0, int(inorder.size() - 1));
    }
};