654. 最大二叉树

难度中等215收藏分享切换为英文接收动态反馈

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

1. 二叉树的根是数组中的最大元素。
2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：
  	  6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

解题思路：

递归：

构造函数 construct(int[] nums,int l,int r) 表示构造数组nums， l -> r 的最大二叉树

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums,0,nums.length);
    }
    public TreeNode construct(int[] nums,int l,int r){
        if(r == l) 
        return null;

        int max_i = max(nums,l,r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums,l,max_i);
        root.right = construct(nums,max_i+1,r);
        return root;
    }
    public int max(int[] nums,int l,int r){
        int max_i = l;
        //System.out.println("ser"+max_i);
        for(int i = l;i < r;i++){
            if(nums[max_i] < nums[i])
             max_i = i;
        }
        //System.out.println(max_i);
        return max_i;
    }
}

总结：

​ 有关于二叉树的题目一般要想到递归，对于此题，题目要求构造二叉树，并且是最大二叉树

那么，我们要想到构造二叉树显然是一个递归的过程，递归构造二叉树分为两个过程—递归构造左子树，递归构造右子树

我们就想到函数 construct 带有三个参数，分别是 数组nums 左边界l 右边界r

在函数内，自然通过改变 l 和 r来在函数体内进行递归

题目要求构造最大二叉树，因此我们需要找到数组中最大的数，以此为分界点，左边为左子树，右边为右子树

root.left = construct(nums,l,max_i);
root.right = construct(nums,max_i+1,r);

由此得到左子树，右子树，这样递归就完成了，返回根节点root即可