Construct Tree from given Inorder and Preorder traversals | GeeksforGeeks
http://www.programcreek.com/2014/06/leetcode-construct-binary-tree-from-preorder-and-inorder-traversal-java/
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
for(int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
if(preStart > preEnd || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inRoot = inMap.get(root.val);
int numsLeft = inRoot - inStart;
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
return root;
}
https://leetcode.com/discuss/29229/concise-java-recursive-solution
https://leetcode.com/discuss/16688/here-is-the-iterative-solution-in-java
public TreeNode buildTree(int[] preorder, int[] inorder) { if (inorder.length==0) return null; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode root = new TreeNode(Integer.MIN_VALUE); stack.push(root); int i=0, j=0; TreeNode node = null; TreeNode cur = root; while (j<inorder.length){ if (stack.peek().val == inorder[j]){ node = stack.pop(); j++; } else if (node!=null){ cur = new TreeNode(preorder[i]); node.right = cur; node=null; stack.push(cur); i++; } else { cur = new TreeNode(preorder[i]); stack.peek().left = cur; stack.push(cur); i++; } } return root.left; }
Time Complexity: O(n^2)
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex. ==> error handle inIndex==-1
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
}
http://www.jiuzhang.com/solutions/construct-binary-tree-from-preorder-and-inorder-traversal/
Read full article from Construct Tree from given Inorder and Preorder traversals | GeeksforGeeks
http://www.programcreek.com/2014/06/leetcode-construct-binary-tree-from-preorder-and-inorder-traversal-java/
Consider the following example:
in-order: 4 2 5 (1) 6 7 3 8 pre-order: (1) 2 4 5 3 7 6 8
From the pre-order array, we know that first element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array.
Using the length of left sub-tree, we can identify left and right sub-trees in pre-order array. Recursively, we can build up the tree.
public TreeNode buildTree(int[] preorder, int[] inorder) { int preStart = 0; int preEnd = preorder.length-1; int inStart = 0; int inEnd = inorder.length-1; return construct(preorder, preStart, preEnd, inorder, inStart, inEnd); } public TreeNode construct(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){ if(preStart>preEnd||inStart>inEnd){ return null; } int val = preorder[preStart]; TreeNode p = new TreeNode(val); //find parent element index from inorder int k=0; for(int i=0; i<inorder.length; i++){ if(val == inorder[i]){ k=i; break; } } p.left = construct(preorder, preStart+1, preStart+(k-inStart), inorder, inStart, k-1); p.right= construct(preorder, preStart+(k-inStart)+1, preEnd, inorder, k+1 , inEnd); return p; } |
X. Use HashMap to cache
One improvement: remember to use HashMap to cache the
inorder[] position. This can reduce your solution from 20ms to 5ms.
You can remove preEnd. It's not used for anything.
https://leetcode.com/discuss/29229/concise-java-recursive-solution
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null || inorder==null || inorder.length==0 || preorder.length==0) return null;
TreeNode root = new TreeNode(preorder[0]);
if(preorder.length==1) return root;
int breakindex = -1;
for(int i=0;i<inorder.length;i++) { if(inorder[i]==preorder[0]) { breakindex=i; break;} }
int[] subleftpre = Arrays.copyOfRange(preorder,1,breakindex+1);
int[] subleftin = Arrays.copyOfRange(inorder,0,breakindex);
int[] subrightpre = Arrays.copyOfRange(preorder,breakindex+1,preorder.length);
int[] subrightin = Arrays.copyOfRange(inorder,breakindex+1,inorder.length);
root.left = buildTree(subleftpre,subleftin);
root.right = buildTree(subrightpre,subrightin);
return root;
}
- The Root of the tree is the first element in Preorder Array.
- Find the position of the Root in Inorder Array.
- Elements to the left of Root element in Inorder Array are the left subtree.
- Elements to the right of Root element in Inorder Array are the right subtree.
- Call recursively buildTree on the subarray composed by the elements in the left subtree. Attach returned left subtree root as left child of Root node.
- Call recursively buildTree on the subarray composed by the elements in the right subtree. Attach returned right subtree root as right child of Root node.
- return Root.
https://leetcode.com/discuss/16688/here-is-the-iterative-solution-in-java
public TreeNode buildTree(int[] preorder, int[] inorder) { if (inorder.length==0) return null; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode root = new TreeNode(Integer.MIN_VALUE); stack.push(root); int i=0, j=0; TreeNode node = null; TreeNode cur = root; while (j<inorder.length){ if (stack.peek().val == inorder[j]){ node = stack.pop(); j++; } else if (node!=null){ cur = new TreeNode(preorder[i]); node.right = cur; node=null; stack.push(cur); i++; } else { cur = new TreeNode(preorder[i]); stack.peek().left = cur; stack.push(cur); i++; } } return root.left; }
Time Complexity: O(n^2)
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex. ==> error handle inIndex==-1
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
struct node* buildTree(char in[], char pre[], int inStrt, int inEnd){ static int preIndex = 0; if(inStrt > inEnd) return NULL; /* Pick current node from Preorder traversal using preIndex and increment preIndex */ struct node *tNode = newNode(pre[preIndex++]); /* If this node has no children then return */ if(inStrt == inEnd) return tNode; /* Else find the index of this node in Inorder traversal */ int inIndex = search(in, inStrt, inEnd, tNode->data); /* Using index in Inorder traversal, construct left and right subtress */ tNode->left = buildTree(in, pre, inStrt, inIndex-1); tNode->right = buildTree(in, pre, inIndex+1, inEnd); return tNode;http://www.jiuzhang.com/solutions/construct-binary-tree-from-preorder-and-inorder-traversal/
Read full article from Construct Tree from given Inorder and Preorder traversals | GeeksforGeeks
