题目描述：

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

示例：

给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

解法：

# define PR pair<int, int>

/**

 * 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:

    int binary_search(vector<PR>& lst, int target){

        int l = 0, r = lst.size() -1;

        int mid = 0;

        while(l <= r){

            mid = l + (r-l)/2;

            if(lst[mid].first < target){

                l = mid + 1;

            }else if(lst[mid].first == target){

                return lst[mid].second;

            }else{

                r = mid - 1;

            }

        }

        return -1;

    }

    // method 3: accepted

    TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder, int pl, int pr, int il, int ir, vector<PR>& inlst) {

        if(pl > pr){

            return NULL;

        }else if(pl == pr){

            return new TreeNode(postorder[pr]);

        }else{

            TreeNode* root = new TreeNode(postorder[pr]);

            int mid = binary_search(inlst, postorder[pr]);

            int lsz = mid - il;

            // int rsz = ir - mid;

            root->left = buildTree(postorder, inorder, pl, pl + lsz-1, il, il + lsz-1, inlst);

            root->right = buildTree(postorder, inorder, pl+lsz, pr-1, il + lsz+1, ir, inlst);

            return root;

        }

    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

       // method 3:

        int sz = postorder.size();

        int pl = 0, pr = sz-1;

        int il = 0, ir = sz-1;

        vector<PR> inlst;

        for(int i = 0; i < sz; i++){

            inlst.push_back({inorder[i], i});

        }

        sort(inlst.begin(), inlst.end());

        return buildTree(postorder, inorder, pl, pr, il, ir, inlst);

    }

};

巴特西

leetcode 106. 从中序与后序遍历序列构造二叉树(Construct Binary Tree from Inorder and Postorder Traversal)

题目描述：

示例：

解法：

最新文章

热门文章