LeetCode [106] Construct Binary Tree from Inorder and Postorder Traversal

 106. Construct Binary Tree from Inorder and Postorder Traversal

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

//C++: 48ms /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int n = inorder.size(); return dfs(inorder, postorder, 0, n-1, n); } TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int i, int p, int len){ if(len<=0) return NULL; int root_v = postorder[p]; TreeNode* node = new TreeNode(root_v); int j=i; for(; j<i+len; ++j){ if(inorder[j]==root_v) break; } int len_left = j-i; int len_right = len-1-len_left; node->left = dfs(inorder, postorder, i, p-1-len_right, len_left); node->right = dfs(inorder, postorder, j+1, p-1, len_right); return node; } }; //Java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { Map<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] inorder, int[] postorder) { int n = inorder.length; if(n==0) return null; for(int i=0; i<n; ++i){ map.put(inorder[i], i); } return helper(inorder, postorder, 0, n-1, 0, n-1); } TreeNode helper(int[] inorder, int[] postorder, int il, int ir, int pl, int pr){ int v = postorder[pr]; TreeNode root = new TreeNode(v); int i = map.get(v);//index of v in inorder int lenL = i-il; int lenR = ir-i; if(lenL>0) root.left = helper(inorder, postorder, il, i-1, pl, pl+lenL-1); if(lenR>0) root.right = helper(inorder, postorder, i+1, ir, pl+lenL, pr-1); return root; } }