資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究程式用 C++ 找出和最小的樹層級
假設我們有一棵二叉樹，其根的層級為 1，其孩子的層級為 2，以此類推。我們需要找出最小的層級 X，使層級 X 上所有節點的值之和為最小。因此，如果樹如下所示 -
輸出將為 2，因為其和為 4 – 10 = -6，最小。
要解決此問題，我們將執行以下步驟 -
level := 1，sum := r 的值，ansLevel := level，ansSum := sum
定義佇列 q，將給定節點 r 插入到 q 中
當 q 不為空時
capacity := q 的大小
level 加 1，sum := 0
當 capacity 不為 0 時
node := q 中的隊首結點，從 q 中刪除該結點
如果該結點的右側有效，則 sum := sum + 右側結點的值，插入右側
- 結點到 q 中
如果該結點的左側有效，則 sum := sum + 左側結點的值，將左側結點插入 q 中
capacity 減 1
如果 ansSum < sum，則 ansSum := sum，ansLevel := level
返回 ansLevel
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
int solve(TreeNode* r) {
int level = 1, sum = r->val;
int ansLevel = level, ansSum = sum;
queue <TreeNode*> q;
q.push(r);
while(!q.empty()){
int capacity = q.size();
level++;
sum = 0;
while(capacity--){
TreeNode* node = q.front();
q.pop();
if(node->right){
sum += node->right->val;
q.push(node->right);
}
if(node->left){
sum += node->left->val;
q.push(node->left);
}
}
if(ansSum>sum){
ansSum = sum;
ansLevel = level;
}
}
return ansLevel;
}
};
main(){
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(-10);
root->left->right = new TreeNode(-2);
root->right->left = new TreeNode(-7);
root->right->right = new TreeNode(15);
Solution ob;
cout <<ob.solve(root);
}輸入
TreeNode *root = new TreeNode(5); root->left = new TreeNode(4); root->right = new TreeNode(-10); root->left->right = new TreeNode(-2); root->right->left = new TreeNode(-7); root->right->right = new TreeNode(15);
輸出
2
更新於: 10-10-2020
234 次瀏覽
廣告