2014年4月22日 星期二

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

Problem:
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:O(n)
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }
 
    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, 
                            int[] postorder, int postStart, int postEnd){
        if(inStart > inEnd || postStart > postEnd)
            return null;
        int rootValue = postorder[postEnd];
        TreeNode root = new TreeNode(rootValue);
        int k=0;
        for(int i=0; i< inorder.length; i++){
            if(inorder[i]==rootValue){
                k = i;
                break;
            }
        }
        root.left = buildTree(inorder, inStart, k-1, postorder, postStart, postStart+k-(inStart+1));
        root.right = buildTree(inorder, k+1, inEnd, postorder, postStart+k-inStart, postEnd-1);
        return root;
    }
}

沒有留言:

張貼留言