-
Notifications
You must be signed in to change notification settings - Fork 1
/
654-最大二叉树.cpp
71 lines (57 loc) · 1.69 KB
/
654-最大二叉树.cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。
示例 :
输入:[3,2,1,6,0,5]
输出:返回下面这棵树的根节点:
6
/ \
3 5
\ /
2 0
\
1
*/
#include<iostream>
using namespace std;
#include<vector>
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(): val(0), left(NULL), right(NULL) {}
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
class Solution{
private:
TreeNode *traversal(vector<int> &nums, int left, int right)
{
if (left >= right){ // 递归终止条件
return nullptr;
}
int maxValueIndex = left;
// 遍历数组找到数组中的最大值
for (int i = left + 1; i < right; i++)
{
if (nums[i] > nums[maxValueIndex])
{
maxValueIndex = i;
}
}
// 将最大值作为根节点
TreeNode *root = new TreeNode(nums[maxValueIndex]);
// 递归左子树,范围左闭右开
root->left = traversal(nums, left, maxValueIndex);
// 递归右子树,范围左闭右开
root->right = traversal(nums, maxValueIndex + 1, right);
return root;
}
public:
TreeNode *constructMaximumBinaryTree(vector<int> &nums)
{
return traversal(nums, 0, nums.size());
}
};