MENU

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

2019 年 03 月 13 日 • 阅读: 1067 • LeetCode阅读设置

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:

    3
   / \
  9  20
    /  \
   15   7

链接

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 SubmittedStatusRuntimeMemoryLanguage
4 hours agoAccepted28 ms16.7 MBcpp
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日 星期三