889. Construct Binary Tree from Preorder and Postorder Traversal 根据前序和后序遍历构造二叉树

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@TOC

题目地址：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/

题目描述

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, ..., pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

题目大意

根据先序遍历和后序遍历，重建二叉树。

解题方法

讲道理的话，只知道前序和后序遍历是没法确定一棵二叉树的。所以，这个题指明了不含重复元素，而且如果有多棵二叉树返回其中的一种即可。

其实做法还是很简单的。前序和后序的遍历并没有打乱整棵树的关系，一棵树的节点在两种遍历方式所得到的还都是在一块的。

所以pre[0]是根节点，也就是post[-1];

post[-2]时候右子树的根节点，因此在前序遍历中找到post[-2]的位置idx就能分开两棵子树。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        if not pre or not post: return None
        root = TreeNode(pre[0])
        if len(pre) == 1:
            return root
        idx = pre.index(post[-2])
        root.left = self.constructFromPrePost(pre[1:idx], post[:idx-1])
        root.right = self.constructFromPrePost(pre[idx:], post[idx-1:-1])
        return root

下面C++代码为了防止平凡的构建子数组，所以使用索引的方式切割数组。C++中，如果函数使用传值的方式进行参数传递，就会调用对象的拷贝构造函数，使得代码效率变慢。所以，一般使用传引用的方式加快函数传参的次数。下面的代码中，pre 和 post使用引用传递，[a,b]表示目前处理的pre区间，[c,d]表示目前处理的post区间。

代码如下：

/**
 * 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* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        const int N = pre.size();
        for (int i = 0; i < N; i++) m_[post[i]] = i;
        return construct(pre, post, 0, N - 1, 0, N - 1);
    }
private:
    unordered_map<int, int> m_;
    // pre[a, b], post[c, d]
    TreeNode* construct(vector<int>& pre, vector<int>& post, int a, int b, int c, int d) {
        TreeNode* root = new TreeNode(pre[a]);
        if (a == b) return root;
        int t = pre[a + 1];
        int idx = m_[t];
        int len = idx - c + 1;
        root->left = construct(pre, post, a + 1, a + len, c, c + len - 1);
        if (idx + 1 == d) return root;
        root->right = construct(pre, post, a + len + 1, b, idx + 1, d - 1);
        return root;
    }
};

参考资料：

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161651/Easy-Python-Recursive-Solution-with-Explanation

日期

2018 年 9 月 4 日 ———— 迎接明媚的阳光！ 2018 年 12 月 8 日 —— 今天球打的不错，很舒服