Question

Formatted question description: https://leetcode.ca/all/106.html

106. 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

@tag-tree

Algorithm

The last one in the post-order sequence must be the root, so the root node of the original binary tree can be known. A very key condition is given in the title that there are no identical elements in the tree.

With this condition, we can also locate in the in-order traversal to find the position of the root node, and split the in-order traversal into the left and right parts according to the position of the root node, and call the original function on it recursively

Code

Java

  • import java.util.Arrays;
    
    public class Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal {
    
    	/**
    	 * Definition for binary tree
    	 * public class TreeNode {
    	 *     int val;
    	 *     TreeNode left;
    	 *     TreeNode right;
    	 *     TreeNode(int x) { val = x; }
    	 * }
    	 */
    
    	public class Solution {
    	    public TreeNode buildTree(int[] inorder, int[] postorder) {
    
                return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
            }
            TreeNode buildTree(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight) {
                if (iLeft > iRight || pLeft > pRight) return null;
                TreeNode cur = new TreeNode(postorder[pRight]);
                int i = 0;
                for (i = iLeft; i < inorder.length; ++i) {
                    if (inorder[i] == cur.val) break;
                }
                cur.left = buildTree(inorder, iLeft, i - 1, postorder, pLeft, pLeft + (i - iLeft - 1));
                cur.right = buildTree(inorder, i + 1, iRight, postorder, pLeft + (i - iLeft), pRight - 1); // (i - iLeft) is (i - iLeft - 1 + 1)
                return cur;
            }
    	}
    }
    
    
  • // OJ: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
    // Time: O(N^2)
    // Space: O(H)
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            function<TreeNode*(int, int, int, int)> build = [&](int is, int ie, int ps, int pe) -> TreeNode* {
                if (is == ie) return NULL;
                auto n = new TreeNode(postorder[pe - 1]);
                int mid = find(begin(inorder) + is, begin(inorder) + ie, n->val) - begin(inorder);
                n->left = build(is, mid, ps, ps + mid - is);
                n->right = build(mid + 1, ie, ps + mid - is, pe - 1);
                return n;
            };
            return build(0, inorder.size(), 0, postorder.size());
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if inorder and postorder:
          postorder.reverse()
          self.index = 0
          d = {}
          for i in range(0, len(inorder)):
            d[inorder[i]] = i
          return self.dfs(inorder, postorder, 0, len(postorder) - 1, d)
    
      def dfs(self, inorder, postorder, start, end, d):
        if start <= end:
          root = TreeNode(postorder[self.index])
          mid = d[postorder[self.index]]
          self.index += 1
          root.right = self.dfs(inorder, postorder, mid + 1, end, d)
          root.left = self.dfs(inorder, postorder, start, mid - 1, d)
          return root
    
    

All Problems

All Solutions