力扣：654. 最大二叉树

其实只需要每一次遍历的时候，找到最大的数组下标就行了。然后遍历既可以得到结果

package com.算法专练.力扣.最大二叉树;
 
import java.util.Arrays;
 
/**
 * @author xnl
 * @Description:
 * @date: 2022/8/20   22:05
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {3,2,1,6,0,5};
        System.out.println(solution.constructMaximumBinaryTree(arr));
    }
 
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length ==0){
            return null;
        }
        int maxIndex = 0;
        int maxValue = nums[0];
        for (int i = 1; i < nums.length; i++){
            if (nums[i] > maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        TreeNode node = new TreeNode(maxValue);
        node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxIndex));
        node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxIndex + 1, nums.length));
        return node;
    }
}
 
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

单调栈解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++){
            TreeNode node = new TreeNode(nums[i]);
            while (!deque.isEmpty()){
                TreeNode top = deque.peek(); 
                if (top.val > node.val){
                    deque.push(node);
                    top.right = node;
                    break;
                }
                node.left = deque.poll();
            }
            if (deque.isEmpty()) deque.push(node);
        }
        return deque.peekLast();
    }
}