2015年10月4日星期日

Leetcode 106 Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder 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[] inorder, int[] postorder) {  
     int n=inorder.length;  
     return build(inorder,0,n-1,postorder,0,n-1);  
   }  
   private TreeNode build(int[] inorder, int lo1, int hi1, int[]postorder, int lo2, int hi2) {  
     if (lo1>hi1) return null;  
     TreeNode x=new TreeNode(postorder[hi2]);  
     int i=0;  
     while (inorder[hi1-i]!=postorder[hi2]) i++;  
     x.left=build(inorder,lo1,hi1-i-1,postorder,lo2,hi2-i-1);  
     x.right=build(inorder,hi1-i+1,hi1,postorder,hi2-i,hi2-1);  
     return x;  
   }  
 }  

Solution 2: iterative

没有评论:

发表评论