Given preorder and inorder traversal of a tree, construct the binary tree.
Solution:O(n)
public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null || preorder.length != inorder.length || preorder.length ==0) return null; return buildTreeHelper(preorder,inorder); } public TreeNode buildTreeHelper(int[] preorder, int[] inorder){ if(preorder == null || inorder == null || preorder.length != inorder.length || preorder.length ==0) return null; TreeNode root = new TreeNode(preorder[0]); int rootindex = 0; for(rootindex=0; rootindex<inorder.length;rootindex++){ if(inorder[rootindex] == preorder[0]) break; } int [] subleftinorder = Arrays.copyOfRange(inorder, 0, rootindex); int [] subleftpreorder = Arrays.copyOfRange(preorder, 1, rootindex+1); root.left = buildTreeHelper(subleftpreorder,subleftinorder); int [] subrightinorder = Arrays.copyOfRange(inorder, rootindex+1, inorder.length); int [] subrightpreorder = Arrays.copyOfRange(preorder, rootindex+1, preorder.length); root.right = buildTreeHelper(subrightpreorder,subrightinorder); return root; } }
沒有留言:
張貼留言