数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++最大二叉树
假设我们有一个整数数组。数组中的所有元素都是唯一的。在此数组上构建的最大树定义如下：
根节点将包含数组中的最大数字。
左子树是由最大数字划分出的子数组左侧构建的最大树。
右子树是由最大数字划分出的子数组右侧构建的最大树。
我们必须构造最大二叉树。因此，如果输入类似：[3,2,1,6,0,5]，则输出将为：
为了解决这个问题，我们将遵循以下步骤：
定义一个名为solve()的方法，它将接收列表和左右值。该函数的工作原理如下：
如果 left > right，则返回 null
maxIndex := left 和 maxVal := nums[left]
对于 i 在 left + 1 到 right 的范围内
如果 maxVal < nums[i]，则 maxVal := nums[i]，maxIndex := i
定义一个值为 maxVal 的节点
节点的左子节点 := solve(nums, left, maxIndex - 1)
节点的右子节点 := solve(nums, maxIndex + 1, right)
返回节点
solve 方法将在主程序部分中调用，方法为：solve(nums, 0, nums 数组长度 - 1)
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(vector <int>& nums, int left, int right){
if(left>right)return NULL;
int maxIndex = left;
int maxVal = nums[left];
for(int i = left + 1; i <= right; i++){
if(maxVal < nums[i]){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode* node = new TreeNode(maxVal);
node->left = solve(nums, left, maxIndex - 1);
node->right = solve(nums, maxIndex + 1, right);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return solve(nums, 0, nums.size() - 1);
}
};
main(){
vector<int> v = {4,3,2,7,1,6};
Solution ob;
inord(ob.constructMaximumBinaryTree(v));
}输入
[3,2,1,6,0,5]
输出
4 3 2 7 1 6
更新于：2020年4月30日
547 次浏览
广告