C++ 中二叉树的最大层级和


假设我们有一个二叉树的根节点,其根节点的层级为 1,其子节点的层级为 2,依此类推。我们需要返回层级 X 的最小值,使得层级 X 上所有节点值的总和最大。如果树如下所示:

则输出将为 2。层级 1 的总和 = 1,层级 2 的总和为 7 + 0 = 7,层级 3 的总和为 7 + (-8) = -1,因此最大值为层级 2,所以输出为 2。

为了解决这个问题,我们将遵循以下步骤:

  • level := 1,sum := r 的值,ansLevel := level,ansSum := sum
  • 定义一个队列 q,将给定的节点 r 插入到 q 中
  • 当 q 不为空时
    • capacity := q 的大小
    • 将 level 增加 1,sum := 0
    • 当 capacity 不为 0 时
      • node := q 中的第一个节点,从 q 中删除该节点
      • 如果 node 的右子节点有效,则 sum := sum + 右子节点的值,并将右子节点插入到 q 中
      • 如果 node 的左子节点有效,则 sum := sum + 左子节点的值,并将左子节点插入到 q 中
      • 将 capacity 减 1
    • 如果 ansSum < sum,则 ansSum := sum,ansLevel := level
  • 返回 ansLevel

示例(C++)

让我们看一下以下实现,以便更好地理解:

 在线演示 在线演示

#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;
}
class Solution {
public:
   int maxLevelSum(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(){
   vector<int> v = {1,7,0,7,-8,NULL,NULL};
   TreeNode *root = make_tree(v);
   Solution ob;
   cout <<ob.maxLevelSum(root);
}

输入

[1,7,0,7,-8,null,null]

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

2

更新于: 2020-04-30

217 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告