leetcode题解-106-从中序与后序遍历序列构造二叉树

发表于 | 更新于 | 分类于

题目

hareyukai way

递归实现 + 参数传迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {        
        return buildTree(rbegin(inorder), rend(inorder),
                         rbegin(postorder), rend(postorder));
    }
    
    template<typename RandomIt>
    TreeNode* buildTree(RandomIt in_rfirst, RandomIt in_rlast,
                        RandomIt post_rfirst, RandomIt post_rlast) {
        if (in_rfirst == in_rlast) return nullptr;
        if (post_rfirst == post_rlast) return nullptr;
        
        auto root = new TreeNode(*post_rfirst);
        
        auto inRootRPos = find(in_rfirst, in_rlast, *post_rfirst);
        auto RightSize = distance(in_rfirst, inRootRPos);
        
        root->right = buildTree(in_rfirst,
                                next(in_rfirst, RightSize),
                                next(post_rfirst),
                                next(post_rfirst, RightSize + 1));
        root->left = buildTree(next(inRootRPos),
                               in_rlast,
                               next(post_rfirst, RightSize + 1),
                               post_rlast);
        return root;
    }
};

简单修改了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
using It = vector<int>::reverse_iterator;

class Solution {
private:
    TreeNode* buildTree(It inFir, It inLast, It postFir, It postLast)
    {
        if (inFir == inLast || postFir == postLast) return nullptr;

        auto root = new TreeNode(*postFir);

        auto inRootPos = find(inFir, inLast, *postFir);
        auto RightSize = distance(inFir, inRootPos);

        root->right = buildTree(inFir, next(inFir, RightSize), next(postFir), next(postFir, RightSize + 1));
        root->left = buildTree(next(inRootPos), inLast, next(postFir, RightSize + 1), postLast);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        return buildTree(inorder.rbegin(), inorder.rend(), postorder.rbegin(), postorder.rend());
    }
};