LeetCode654 Maximum Binary Tree

文章目录
  1. 1. 题目
  2. 2. 思路
  3. 3. 代码

题目

LeetCode654 Maximum Binary Tree

思路

递归构造二叉搜索树,树的左右儿子都比父结点小.

代码

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* helper(vector<int>& nums, int l, int r) {
TreeNode* node = new TreeNode(0);
int num = nums[l], id = l;
for (int i = l; i <= r; ++i) {
if (num < nums[i]) {
num = nums[i];
id = i;
}
}
node->val = num;
if (l <= id - 1) node->left = helper(nums, l, id - 1);
if (id + 1 <= r) node->right = helper(nums, id + 1, r);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
};
分享到 评论