資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告