LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal


和LeetCode105( https://ask.julyedu.com/article/388 )差不多,在中序序列中找到根节点的位置,然后计算左子树的数量,剩下就是105的传递下标了,代码如下:
/**
 * 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0){
            return NULL;
        }
        
        TreeNode *root = NULL;
        
        root = ConstructTree(root, inorder, 0, inorder.size() - 1, postorder, 0,  postorder.size() - 1);
        
        return root;
    }
    
    TreeNode *ConstructTree(TreeNode *root, vector<int> &in, int st1, int end1, vector<int> &post, int st2, int end2){
        if (st1 > end1 || end2 < 0){
            return NULL;
        }
        
        root = new TreeNode(post[end2]);
        
        int pos = -1;
        for (int i = st1; i <= end1; ++i){
            if (post[end2] == in[i]){
                pos = i;
                break;
            }
        }
        
        if (pos == -1){
            return NULL;
        }
        
        int nLeft = pos - st1;
        root->left  = ConstructTree(root, in, st1,     pos - 1, post, st2,         st2 + nLeft - 1);
        root->right = ConstructTree(root, in, pos + 1, end1,    post, st2 + nLeft, end2 - 1);
        
        return root;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部