LeetCode105. Construct Binary Tree from Preorder and Inorder Traversal（二叉树 / 思维）

Medium
Accepted：203,795
Submissions：513,642

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

链接

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

题意

给定一颗二叉树的前序遍历和中序遍历，还原这棵二叉树。

题解

怎么还原呢？很简单。对于前序：根左右，中序：左根右，后序：左右根。给定了前序遍历后我们就可以唯一确定根节点，即最左边的元素，然后找到根节点在中序遍历中的位置，那么位置左边的就是左子树，位置右边的就是右子树，然后接着对左右子树进行相同的处理那么就可以确定整棵二叉树了。

3 [9] [20, 15, 7] // 根 左 右
[9] 3 [15, 20, 7] // 左 右 根

20 [15] [7] // 根 左 右
[15] 20 [7] // 左 右 根

事实上只要（中序 + 前序 / 后序）就可以唯一确定一颗二叉树，而（前序 + 后序）能得到一颗二叉树，但不是唯一的，做法也类似，确定根节点的位置后划分左右子树再递归处理。比如LeetCode889. Construct Binary Tree from Preorder and Postorder Traversal（二叉树 / 思维）。

[3] 9 20 15 7 // 根 左 右
9 15 7 20 [3] // 左 右 根
    
然后我们可以假定前序中的9是一个根节点，然后找到9在后序中的位置。

[9] 20 15 7
[9] 15 7 20
    
后序中9的左边没有元素了，说明9就是左子树，而9右边的[15, 7, 20]就是右子树，接下来的处理类似。

时间复杂度的话是$T(n) = 2T(n/2) + n$，为$O(n^2)$，如果把查找根节点在后序遍历中的位置优化一下，使用unordered_map来存储的话，可以将时间复杂度降到$O(n)$。

此外，如果数组保存的话，可以更简单实现，因为可以传递数组首元素地址，但是使用vector的话就得控制一下是从哪里开始，然后长度是多少，比较麻烦。

代码

Time Submitted	Status	Runtime	Memory	Language
4 hours ago	Accepted	28 ms	16.7 MB	cpp

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        return solve(preorder, inorder, 0, 0, n);
    }

private:
    TreeNode* solve(vector<int>& preorder, vector<int>& inorder, int preStart, int inStart, int size)
    {
        if (size <= 0)
            return NULL;
        int root = preorder[preStart], pos = 0; // pos代表根节点在后序遍历中位置，默认为0
        for (int i = inStart; i < inStart + size; ++i)
        {
            if (inorder[i] == root)
            {
                pos = i;
                break;
            }
        }
        TreeNode* bt = new TreeNode(root);
        pos = (pos == 0) ? pos : pos - inStart; // 之前是从inStart的所以要减去
        bt->left = solve(preorder, inorder, preStart + 1, inStart, pos);
        bt->right = solve(preorder, inorder, preStart + pos + 1, inStart + pos + 1,  size - pos - 1);
        return bt;
    }
};

被pos坑了，很久才找到错误。

The end.
2019年3月13日星期三