Inorder Traversal of Cartesian Tree

Given an inorder traversal of a cartesian tree, construct the tree.

Input : [1 2 3]

Return :   
          3
         /
        2
       /
      1

Method:

Find the largest number and use it as root, use the index to split array into left and right, and then recursively set left and right child.

Solution:

Time: O(nlogn)
Space: O(n)

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    public TreeNode buildTree(ArrayList<Integer> A) {
        if (A.size() == 0) return null;
        int maxVal = Integer.MIN_VALUE;
        int maxIndex = 0;
        for (int i = 0; i < A.size(); i ++) {
            if (A.get(i) > maxVal) {
                maxVal = A.get(i);
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        root.left = buildTree(new ArrayList<Integer>(A.subList(0, maxIndex)));
        root.right = buildTree(new ArrayList<Integer>(A.subList(maxIndex + 1, A.size())));
        return root;
    }
}