Max Tree

Question

from lintcode

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

The root is the maximum number in the array
The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.

Example
Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

    6
   / \
  5   3
 /   / \
2   0   1

Idea

Using recursion is simple. Build a tree with first element, then keep inserting continued elements into the tree recursively by enforcing such a rule:

Put each inserted element into the right subtree if it is smaller than root. If it is bigger than root, let root be the left subtree of this inserted element.

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

/*
  It is guaranteed that there are no duplicates;
*/
public class Solution {
    /*
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        TreeNode root = null;
        for(int x : A) {
            root = insert(root, x);
        }
        return root;
    }
    
    private TreeNode insert(TreeNode node, int x) {
        TreeNode xnode = new TreeNode(x);
        if (node == null)
          return xnode;
        if (xnode.val > node.val) {
          xnode.left = node;
          return xnode;
        } else {
          node.right = insert(node.right, x);
          return node;
        }
    }
}