时间戳

首页 > 解决方案 > 检查二叉树的级别之和是否相等

c++ - 检查二叉树的级别之和是否相等

问题描述

我试图在 C++ 中找出一个函数来计算二叉树的所有级别的总和，然后检查这些总和是否都相等，如果相等则返回 TRUE。

例如，如果第一个节点是 10，则其子节点之和必须为 10，其子节点之和必须为 10，以此类推......

在没有递归妨碍的情况下，我在比较总和时遇到了麻烦。并且必须在函数本身而不是主函数中进行比较。

如果你能弄清楚这将是非常有帮助的。谢谢

标签： c++binary-tree

解决方案

如果您已按如下方式定义节点数据

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

然后您可以执行没有递归的级别顺序遍历，如下所示。

  1. 初始化队列
  2. 将根节点存储在队列中
  3. 现在遍历children，直到队列为空
  4. 遍历时，如果找到左或右孩子，则必须再次将它们推入队列

这是执行您想要的基本代码

bool equalSums(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        
        queue<TreeNode*> q;
        
        //push the root
        q.push(root);

        int sum = root->val; //save the current root value

        int len;
        TreeNode *temp;

        while(!q.empty()){
            int s = 0; //keep track of the next levels sum

            len = q.size(); //size of queue is number of elements at that level
            
            for(int i=0; i<len; i++){
                temp = q.front();
                q.pop();
                
                s = s+temp->val;
                
                if(temp->left)
                    q.push(temp->left);
                if(temp->right)
                    q.push(temp->right);
            }
            
            // break if sum is not equal to sum of node values in current level
            if(s != sum)
                return false;
        }
        
        // else return true
        return true;
    }

我希望这回答了你的问题。

推荐阅读