一起学习交流~

从前序/后序与中序遍历序列构造二叉树

算法 laomuji 7个月前 (03-03) 430次浏览 已收录 0个评论

题目

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

题目链接
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

前序和中序构造

/**
 * 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 {
    unordered_map<int,int>inorderMap;//便于快速搜索中序遍历中的下标
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i =0;i<inorder.size();i++){
            inorderMap[inorder[i]]=i;//将中序遍历的值对应下标
        }
        return dfs(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* dfs(vector<int>& preorder,vector<int>& inorder,int preLeft,int preRight,int inLeft,int inRight){
        if(preLeft > preRight || inLeft >inRight)return nullptr;
        int preRoot = preLeft;
        int inRoot = inorderMap[preorder[preRoot]];
        int leftSize = inRoot - inLeft;
        TreeNode*cur = new TreeNode(preorder[preRoot]);
        cur->left =  dfs(preorder,inorder,preLeft+1,preLeft+leftSize,inLeft,inRoot-1);
        cur->right = dfs(preorder,inorder,preLeft+leftSize+1,preRight,inRoot+1,inRight);
        return cur;
    }
};

后序和中序构造

/**
 * 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 {
    unordered_map<int,int>inorderMap;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i =0;i<inorder.size();i++){
            inorderMap[inorder[i]]=i;
        }
        return dfs(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder,int inStart,int inEnd,int postStart,int postEnd){
        if(inStart>inEnd || postStart>postEnd)return nullptr;
        int postRoot = postEnd;
        TreeNode*root = new TreeNode(postorder[postRoot]);
        int inRoot = inorderMap[postorder[postRoot]];
        int leftSize  = inRoot-inStart;
        int rightSize = inEnd-inRoot;
        root->left  = dfs(inorder,postorder,inStart ,inRoot-1,postStart,postRoot-rightSize-1);
        root->right = dfs(inorder,postorder,inRoot+1,inEnd   ,postStart+leftSize,postRoot-1);
        return root;
    }
};
喜欢 (2)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论