检查二叉树的层次之和是否相等

Question

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

例如，如果第一个节点是 10，那么它的子节点的总和必须是 10，它们的子节点的总和必须是 10，依此类推...

在没有递归妨碍的情况下，我无法比较总和。并且必须在函数本身而不是 main 中进行比较。

如果你能弄清楚，那将非常有帮助。谢谢

Answer 1

如果您已经如下定义了节点数据

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) {}
};

然后可以如下进行无递归的层序遍历

初始化队列
将根节点存入队列
现在遍历子节点直到队列为空
遍历时，如果找到左孩子或右孩子，则必须将他们再次推入队列

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

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;
    }

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

检查二叉树的层次之和是否相等

Checking if the sums of the levels of a Binary Tree are equal

c++

binary-tree