MaximumBinaryTree [source code]

public class MaximumBinaryTree {
static
/******************************************************************************/
public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int[] nums, int lo, int hi) {
        if (lo == hi)
            return new TreeNode(nums[lo]);
        int max = Integer.MIN_VALUE, maxIndex = lo;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        TreeNode res = new TreeNode(max);
        if (maxIndex - 1 >= lo)
            res.left = build(nums, lo, maxIndex - 1);
        if (maxIndex + 1 <= hi)
            res.right = build(nums, maxIndex + 1, hi);
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaximumBinaryTree.Solution tester = new MaximumBinaryTree.Solution();
    }
}

题目意思好像不是很难懂, 但是是一个medium的题目, 感觉是不是有坑? 不管了, 先写一个笨办法, 如果有坑, 在中途自己再修改算了. 如果是完全没有思路, 那么你绞尽脑汁想可以, 但是如果有一个大概的思路, 就先写, 不要一行代码还没有写出来就先开始绞尽脑汁想优化;

recursion算法的debug, 尤其是overflow的debug, 一个很好的技巧就是打印calling arguments;

暂时也想不到什么好的写法, 笨办法其实就很简单, 标准的divide&conquer做法就是了, 最后的时间是15ms (N/A). 暂时不知道percentile是多少, 题目太新了;

discussion最优解, 基本差不多的写法:

public class Solution {  
    public TreeNode constructMaximumBinaryTree(int[] nums) {  
        if (nums == null) return null;  
        return build(nums, 0, nums.length - 1);  
    }  

    private TreeNode build(int[] nums, int start, int end) {  
        if (start > end) return null;  

        int idxMax = start;  
        for (int i = start + 1; i <= end; i++) {  
            if (nums[i] > nums[idxMax]) {  
                idxMax = i;  
            }  
        }  

        TreeNode root = new TreeNode(nums[idxMax]);  

        root.left = build(nums, start, idxMax - 1);  
        root.right = build(nums, idxMax + 1, end);  

        return root;  
    }  
}

注意人家记得判断了Empty case;

看了一下, 基本还没有什么好的新方法. 暂时不管了;

Problem Description

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]  
Output: return the tree root node representing the following tree:  

      6  
    /   \  
   3     5  
    \    /   
     2  0     
       \  
        1

Note:

• The size of the given array will be in the range [1,1000].

Difficulty:Medium
Total Accepted:1.9K
Total Submissions:2.5K
Contributor: symplecticgeometry
Companies
microsoft
Related Topics
tree