2015年10月4日星期日

Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Solution 1: recursive
 public class Solution {  
   public TreeNode buildTree(int[] preorder, int[] inorder) {  
     int n=preorder.length;  
     return build(preorder,0,n-1,inorder,0,n-1);  
   }  
   private TreeNode build(int[] pre, int l1, int h1, int[] in, int l2, int h2) {  
     if (l1>h1) return null;  
     TreeNode x=new TreeNode(pre[l1]);  
     int i=0;  
     while (in[l2+i]!=pre[l1]) i++;  
     x.left=build(pre,l1+1,l1+i,in,l2,l2+i-1);  
     x.right=build(pre,l1+i+1,h1,in,l2+i+1,h2);  
     return x;  
   }  
 }  

Solution 2: iterative (use stack)

没有评论:

发表评论