package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * 654. Maximum Binary Tree
 *
 * Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
 *
 * The root is the maximum number in the array.
 * The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
 * 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].
 */
public class _654 {

    public static class Solution1 {
        /**
         * Completely my original solution:
         *
         * As the problem states, I always broke the array into two halves and make notes
         * of current max node, then in the recursive call, we can recursively search
         * from its left part to construct its left subtree and its right part to construct its
         * right subtree.*/
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            int max = Integer.MIN_VALUE;
            int maxIndex = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > max) {
                    max = nums[i];
                    maxIndex = i;
                }
            }
            TreeNode root = new TreeNode(max);
            return constructMaxTree(root, maxIndex, nums, 0, nums.length - 1);
        }

        private TreeNode constructMaxTree(TreeNode root, int rootIndex, int[] nums, int start, int end) {
            if (rootIndex > start) {
                int max = Integer.MIN_VALUE;
                int maxIndex = -1;
                for (int i = start; i < rootIndex; i++) {
                    if (max < nums[i]) {
                        max = nums[i];
                        maxIndex = i;
                    }
                }
                root.left = constructMaxTree(new TreeNode(max), maxIndex, nums, start, rootIndex - 1);
            }
            if (rootIndex < end) {
                int max = Integer.MIN_VALUE;
                int maxIndex = -1;
                for (int i = rootIndex + 1; i <= end; i++) {
                    if (max < nums[i]) {
                        max = nums[i];
                        maxIndex = i;
                    }
                }
                root.right = constructMaxTree(new TreeNode(max), maxIndex, nums, rootIndex + 1, end);
            }
            return root;
        }
    }

    public static class Solution2 {
        /**
         * Completely my original solution as well, but more concise.
         */
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if (nums == null || nums.length == 0) {
                return null;
            }
            return construct(nums, 0, nums.length - 1);
        }

        TreeNode construct(int[] nums, int start, int end) {
            if (start > end) {
                return null;
            }
            int[] maxArray = findMax(nums, start, end);
            TreeNode root = new TreeNode(maxArray[0]);
            root.left = construct(nums, start, maxArray[1] - 1);
            root.right = construct(nums, maxArray[1] + 1, end);
            return root;
        }

        int[] findMax(int[] nums, int start, int end) {
            int max = nums[start];
            int maxIndex = start;
            for (int i = start + 1; i <= end; i++) {
                if (max < nums[i]) {
                    maxIndex = i;
                    max = nums[i];
                }
            }
            return new int[]{max, maxIndex};
        }
    }
}

@@ -82,727 +82,8 @@
 e;%0A%0A
-/**%0A * 654. Maximum Binary Tree%0A *%0A * Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:%0A *%0A * The root is the maximum number in the array.%0A * The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.%0A * The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.%0A * Construct the maximum tree by the given array and output the root node of this tree.%0A%0A Example 1:%0A Input: %5B3,2,1,6,0,5%5D%0A Output: return the tree root node representing the following tree:%0A%0A    6%0A  /   %5C%0A 3    5%0A  %5C   /%0A  2  0%0A   %5C%0A   1%0A%0A Note:%0A The size of the given array will be in the range %5B1,1000%5D.%0A */%0A
 publ
@@ -201,16 +201,20 @@
        *
+ %3Cp%3E
 %0A       
@@ -478,16 +478,16 @@
 uct its%0A
-
         
@@ -503,16 +503,26 @@
 subtree.
+%0A         
 */%0A     

refactor 654