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

题目的目标是使用所给的数组按照要求构建一个二叉树，根节点是数值最大的，左儿子的值小于根节点，右儿子的值大于根节点。 思路是先找到一组数组中值最大的节点，该节点位置左边的数放入左子树数组，右边的数放入右子树数组，然后分别对这两个数组进行递归调用，继续这样构造子树。递归的结束条件是判断传入参数的数组是否为空，如果为空则返回null

js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 */
function TreeNode(val){
    this.val = val;
    this.left = this.right = null;
}
 
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    if(nums.length==0){
        return null;
    }
    var max = 0;
    var max_index = 0;
    for(let i=0; i<nums.length; i++){ 
        if(nums[i]<max){
            max = nums[i];
            max_index = i;
        }
    }
    var treenode = new TreeNode(max);
    var leftnums = nums.slice(0,max_index),
        rightnums =nums.slice(max_index+1,nums.length+1);
 
    treenode.left = constructMaximumBinaryTree(leftnums);
    treenode.right = constructMaximumBinaryTree(rightnums);
 
    return treenode
 
};

c++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        //判断递归终止条件
        if(nums.size()==0){
            return NULL;
        }
        //找到最大的树节点
        int max = 0;
        int max_index = 0;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > max){
                max = nums[i];
                max_index = i;
            }
        }
        //递归构造二叉树
        vector<int> leftnums = {};
        vector<int> rightnums = {};
        TreeNode* treenode = new TreeNode(max);
        for(int i=0; i<max_index; i++){
            leftnums.push_back(nums[i]);
        }
        for(int i=max_index+1; i<nums.size(); i++){
            rightnums.push_back(nums[i]);
        }
        treenode->left = constructMaximumBinaryTree(leftnums);
        treenode->right = constructMaximumBinaryTree(rightnums);
     
        return treenode;
    }
};