Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

 Given preorder and inorder traversal of a tree, construct the binary tree.

------------------------------------- read codes ---------------------------------------------------------
https://oj.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; }

------------------------------ codes ---------------------------------------------------
/** * 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> &preorder, vector<int> &inorder) { if (preorder.size() == 0) { return NULL; } return buildHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } TreeNode *buildHelper(vector<int> &preorder, int pre_i, int pre_j, vector<int> &inorder, int in_i, int in_j) { TreeNode *ele = new TreeNode(preorder[pre_i]); if (in_i == in_j) { return ele; } //find node's position int i; for (i = in_i; i <= in_j; i++) { if (inorder[i] == preorder[pre_i]) { break; } } if (in_i < i) { ele->left = buildHelper(preorder,pre_i+1, pre_i + (i-in_i), inorder, in_i, i - 1); } if (i < in_j) { ele->right = buildHelper(preorder, pre_i + (i-in_i) + 1, pre_j, inorder, i + 1, in_j); } return ele; } };