Construct Binary Tree From Inorder And Postorder Traversal Problem


Description

LeetCode Problem 106.

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

1
2
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

1
2
Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    return create(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}

TreeNode* create(vector<int> &inorder, vector<int> &postorder, int is, int ie, int ps, int pe){
    if(ps > pe){
        return nullptr;
    }
    TreeNode* node = new TreeNode(postorder[pe]);
    int pos;
    for(int i = is; i <= ie; i++){
        if(inorder[i] == node->val){
            pos = i;
            break;
        }
    }
    node->left = create(inorder, postorder, is, pos - 1, ps, ps + pos - is - 1);
    node->right = create(inorder, postorder, pos + 1, ie, pe - ie + pos, pe - 1);
    return node;
}




Related Posts

Sum Root To Leaf Numbers Problem

LeetCode 129. You are given the root of a binary...

Populating Next Right Pointers In Each Node Problem

LeetCode 116. You are given a perfect binary tree where...

Populating Next Right Pointers In Each Node II Problem

LeetCode 117. Given a binary tree, populate each next pointer...

Path Sum Problem

LeetCode 112. Given the root of a binary tree and...

Minimum Depth Of Binary Tree Problem

LeetCode 111. Given a binary tree, find its minimum depth....

Balanced Binary Tree Problem

LeetCode 110. Given a binary tree, determine if it is...