Inorder Traversal of Cartesian Tree.java

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    TreeNode helper(List<Integer> A) {
        if (A == null || A.isEmpty()) {
            return null;
        } else if (A.size() == 1) {
            return new TreeNode(A.get(0));
        }

        int max = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < A.size(); i++) {
            if (A.get(i) > max) {
                max = A.get(i);
                index = i;
            }
        }

        TreeNode head = new TreeNode(max);
        List<Integer> leftList = index > 0 ? A.subList(0, index) : null;
        List<Integer> rightList = index + 1 < A.size() ? A.subList(index + 1, A.size()) : null;

        head.left = helper(leftList);
        head.right = helper(rightList);
        return head;
    }

    public TreeNode buildTree(int[] A) {
        List<Integer> arr = new ArrayList<>();
        for (int num : A) {
            arr.add(num);
        }
        return helper(arr);
    }
}