2014年4月23日 星期三

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Problem:
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;
    }
}

沒有留言:

張貼留言