2014年2月17日星期一

LeetCode - 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.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null || postorder==null || inorder.length!=postorder.length || inorder.length==0) {
            return null;
        }
        TreeNode root = new TreeNode(inorder[inorder.length-1]);
       
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }
   
    private int find(int[] inorder, int inS, int inE, int root) {
        for(int i=inS;i<=inE;i++) {
            if(inorder[i]==root) {
                return i;
            }
        }
        return -1;
    }
   
    private TreeNode build(int[] inorder, int inS, int inE, int[] postorder, int poS, int poE) {
        if(inS>inE || poS>poE) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[poE]);
        int mid = find(inorder, inS, inE, postorder[poE]);
        int leftSize = mid - inS;
        //int rightSize = inE - inS - leftSize;
        root.left = build(inorder, inS, mid -1, postorder, poS, poS+leftSize-1);
        root.right = build(inorder, mid+1, inE, postorder, poS+leftSize, poE-1);
        return root;
    }
}

没有评论:

发表评论