数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告