前序后序构造树

约 23 个字 40 行代码 预计阅读时间 1 分钟

• 该树是不唯一确定的

• 需要确定左子树和右子树的大小

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> map;
    TreeNode * myTree(vector<int>& preorder,vector<int> & postorder,int preorder_left,int preorder_right,int postorder_left,int postorder_right){
        if(preorder_left > preorder_right) return nullptr;
        if (postorder_left > postorder_right) return nullptr;
        int preorder_root = preorder_left;
        int postorder_root = map[preorder[preorder_root]];
        TreeNode * root = new TreeNode(postorder[postorder_root]);
        //这行不加会无限循环
        if (preorder_left == preorder_right) return root;
        //左子树根节点在后序遍历中的位置map[preorder[preorder_left + 1]]
        int size_left = map[preorder[preorder_left + 1]] - postorder_left  + 1;




        root->left = myTree(preorder,postorder,preorder_left + 1, preorder_left + size_left,postorder_left,postorder_left + size_left - 1);
        root->right = myTree(preorder,postorder,preorder_left + size_left  + 1,preorder_right,postorder_left + size_left,postorder_right - 1);
        return root;
    }
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++){
            map[postorder[i]] = i;
        }
        return myTree(preorder,postorder,0,n - 1,0,n -1);
    }
};

颜色主题调整

red pink purple indigo blue cyan teal green lime orange brown grey black white

评论区~

有用的话请给我个赞和 star =>
快来跟我聊天~