It's the Xinrui Ma

Blog

Construct Binary Tree from Inorder and Postorder Traversal

Posted by in LeetCode on

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

Thought:
Inorder: [left, root, right] postorder: [left, right, root]

So from each postorder array, we can get the current Root node for the tree, and use that root node, we can find the left subtree for the root, and the right subtree for the root.
Also we can get the postorder sequence by the number of left subtree nodes, and the number of right subtree nodes.

The end condition is we reach a leaf node, we set it’s left and right child to null, and return that node.