106.Construct Binary Tree from Inorder and Postorder Traversal

---

Tags: Tree Medium

Link: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

---

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

---

Answer:

这里只需要注意两点：

1. 在给root赋值时要*(post_end - 1)
2. 在递归时，很容易写出post_end+1这种，应该是post_end -1

/**
 * 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:
    using Iter = vector<int>::iterator;
    TreeNode* buildTreeFromInAndPost(Iter in_start, Iter in_end, Iter post_start, Iter post_end){
        if(in_start == in_end) return nullptr;
        if(post_start == post_end) return nullptr;

        auto root = new TreeNode(*(post_end - 1));
        auto inRootPos = find(in_start, in_end, *(post_end-1));
        auto rightSzie = distance(inRootPos+1, in_end);

        root -> right = buildTreeFromInAndPost(inRootPos+1, in_end, post_end-1-rightSzie, post_end-1);
        root -> left = buildTreeFromInAndPost(in_start, inRootPos, post_start, post_end - 1 - rightSzie);

        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeFromInAndPost(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
    }
};