问：计算二叉树奇偶层节点和之差的程序。

2025年03月17日 | 阅读 9 分钟

说明

在此程序中，我们需要计算奇数层节点之和与偶数层节点之和的差。假设一棵树有 5 层，那么：

Program to calculate the difference between the sum of the odd level and even level nodes of a Binary Tree

在上图中，奇数层用蓝色虚线表示，偶数层用绿色表示。

OddLevelSum = 1 + 4 + 5 + 6 = 16
EvenLevelSum = 2 + 3 = 5
Difference = |16 - 5| = 11

算法

定义 Node 类，该类有三个属性：data、left 和 right。其中，left 代表节点的左子节点，right 代表节点的右子节点。
创建节点时，将节点的 data 部分赋值为适当的值，并将其 left 和 right 子节点设置为 NULL。
定义另一个类，该类有一个 root 属性。
1. Root 表示树的根节点，初始值为 null。
difference() 函数将计算奇数层和与偶数层和之间的差值。
1. 使用队列逐层遍历二叉树。
2. 使用变量 currentLevel 跟踪当前层。
3. 如果 currentLevel 能被 2 整除，则将当前层所有节点的值加到变量 evenLevel 中。否则，将当前层所有节点的值加到变量 oddLevel 中。
4. 通过从 oddLevel 中减去 evenLevel 中的值来计算差值。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class DiffOddEven:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #difference() will calculate the difference between sum of odd and even levels of binary tree
    def difference(self):
        oddLevel = 0;
        evenLevel = 0;
        diffOddEven = 0;
        
        #Variable nodesInLevel keep tracks of number of nodes in each level
        nodesInLevel = 0;
        
        #Variable currentLevel keep track of level in binary tree
        currentLevel = 0;
        
        #queue will be used to keep track of nodes of tree level-wise
        queue = [];
        
        #Check if root is None
        if(self.root == None):
            print("Tree is empty");
            return 0;
        else:
            #Add root node to queue as it represents the first level
            queue.append(self.root);
            currentLevel = currentLevel + 1;
            
            while(len(queue) != 0):
                #Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
                nodesInLevel = len(queue);
                
                while(nodesInLevel > 0):
                    current = queue.pop(0);
                    
                    #Checks if currentLevel is even or not.
                    if(currentLevel % 2 == 0):
                        #If level is even, add nodes's to variable evenLevel
                        evenLevel = evenLevel + current.data;
                    else:
                        #If level is odd, add nodes's to variable oddLevel
                        oddLevel = oddLevel + current.data;
                        
                    #Adds left child to queue
                    if(current.left != None):
                        queue.append(current.left);
                    #Adds right child to queue
                    if(current.right != None):
                        queue.append(current.right);
                    nodesInLevel = nodesInLevel - 1;
                currentLevel = currentLevel + 1;
            #Calculates difference between oddLevel and evenLevel
            diffOddEven = abs(oddLevel - evenLevel);
        return diffOddEven;    
        
bt = DiffOddEven();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.right.left = Node(5);
bt.root.right.right = Node(6);
 
#Display the difference between sum of odd level and even level nodes
print("Difference between sum of odd level and even level nodes: " + str(bt.difference()));

输出

Difference between sum of odd level and even level nodes: 11

C

#include <stdio.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right child to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//Queue will be used to keep track of nodes of tree level-wise
struct node *queue[100];
int rear = 0, front = -1, size = 0;
 
//Adds a node to queue
void enqueue(struct node *temp){
    queue[rear++] = temp;
    size++;
}
 
//Deletes a node from queue
struct node *dequeue(){
    size--;
    return queue[++front];
}
 
//difference() will calculate the difference between sum of odd and even levels of binary tree
int difference() {
    int oddLevel = 0, evenLevel = 0, diffOddEven = 0;
      
    //Variable nodesInLevel keep tracks of number of nodes in each level
    int nodesInLevel = 0;
    
    //Variable currentLevel keep track of level in binary tree
    int currentLevel = 0;
    
    //Check if root is null
    if(root == NULL) {
        printf("Tree is empty\n");
        return 0;
    }
    else {
        //Add root node to queue as it represents the first level
        enqueue(root);
        currentLevel++;
        
        while(size != 0) {
              
            //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
            nodesInLevel = size;
            
            while(nodesInLevel > 0) {
                  struct node *current = dequeue();
                  
                //Checks if currentLevel is even or not.
                if(currentLevel % 2 == 0)
                    //If level is even, add nodes's to variable evenLevel
                    evenLevel += current->data;
                else
                    //If level is odd, add nodes's to variable oddLevel
                    oddLevel += current->data;
                  
                //Adds left child to queue
                if(current->left != NULL)
                    enqueue(current->left);
                //Adds right child to queue
                if(current->right != NULL) 
                    enqueue(current->right);
                nodesInLevel--;
            }
            currentLevel++;
        }
        //Calculates difference between oddLevel and evenLevel
        diffOddEven = abs(oddLevel - evenLevel);
    }
    return diffOddEven;
  }
    
int main(){
    
    //Add nodes to the binary tree
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->right->left = createNode(5);
    root->right->right = createNode(6);
    
    //Display the difference between sum of odd level and even level nodes
    printf("Difference between sum of odd level and even level nodes: %d", difference());
    
    return 0;
}

输出

Difference between sum of odd level and even level nodes: 11

JAVA

import java.util.LinkedList;
import java.util.Queue;
 
public class DiffOddEven {
    
    //Represent a node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
            }
        }
    
    //Represent the root of binary tree
    public Node root;
  
    public DiffOddEven(){
        root = null;
    }
 
    //difference() will calculate the difference between sum of odd and even levels of binary tree
    public int difference() {
          int oddLevel = 0, evenLevel = 0, diffOddEven = 0;
          
          //Variable nodesInLevel keep tracks of number of nodes in each level
          int nodesInLevel = 0;
          
          //Variable currentLevel keep track of level in binary tree
          int currentLevel = 0;
          
          //Queue will be used to keep track of nodes of tree level-wise
          Queue<Node> queue = new LinkedList<Node>();
          
          //Check if root is null
          if(root == null) {
              System.out.println("Tree is empty");
              return 0;
          }
          else {
              //Add root node to queue as it represents the first level
              queue.add(root);
              currentLevel++;
              
              while(queue.size() != 0) {
                  
                  //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
                  nodesInLevel = queue.size();
                  
                  while(nodesInLevel > 0) {
                      Node current = queue.remove();
                      
                    //Checks if currentLevel is even or not.
                      if(currentLevel % 2 == 0)
                          //If level is even, add nodes's to variable evenLevel
                          evenLevel += current.data;
                      else
                          //If level is odd, add nodes's to variable oddLevel
                          oddLevel += current.data;
                      
                      //Adds left child to queue
                      if(current.left != null)
                          queue.add(current.left);
                      //Adds right child to queue
                      if(current.right != null) 
                          queue.add(current.right);
                     nodesInLevel--;
                  }
                  currentLevel++;
              }
              //Calculates difference between oddLevel and evenLevel
              diffOddEven = Math.abs(oddLevel - evenLevel);
          }
          return diffOddEven;
      }
  
    public static void main (String[] args) {
        
        DiffOddEven bt = new DiffOddEven();
        //Add nodes to the binary tree
        bt.root = new Node(1);
        bt.root.left = new Node(2);
        bt.root.right = new Node(3);
        bt.root.left.left = new Node(4);
        bt.root.right.left = new Node(5);
        bt.root.right.right = new Node(6);
    
        //Display the difference between sum of odd level and even level nodes
        System.out.println("Difference between sum of odd level and even level nodes: " + bt.difference());
}
}

输出

Difference between sum of odd level and even level nodes: 11

C#

using System;
using System.Collections.Generic;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class DiffOddEven<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            T[] treeArray;
            int index = 0;
            
            public DiffOddEven(){
                root = null;
            }
            
            //difference() will calculate the difference between sum of odd and even levels of binary tree
            public int difference() {
                int oddLevel = 0, evenLevel = 0, diffOddEven = 0;
                  
                //Variable nodesInLevel keep tracks of number of nodes in each level
                int nodesInLevel = 0;
                
                //Variable currentLevel keep track of level in binary tree
                int currentLevel = 0;
                
                //Queue will be used to keep track of nodes of tree level-wise
                Queue<Node<T>> queue = new Queue<Node<T>>();
                
                //Check if root is null
                if(root == null) {
                    Console.WriteLine("Tree is empty");
                      return 0;
                }
                else {
                    //Add root node to queue as it represents the first level
                    queue.Enqueue(root);
                    currentLevel++;
                    
                    while(queue.Count != 0) {
                      
                        //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
                        nodesInLevel = queue.Count;
                        
                        while(nodesInLevel > 0) {
                            Node<T> current = queue.Dequeue();
                          
                            //Checks if currentLevel is even or not.
                            if(currentLevel % 2 == 0)
                                //If level is even, add nodes's to variable evenLevel
                                evenLevel += Convert.ToInt32(current.data);
                              else
                                //If level is odd, add nodes's to variable oddLevel
                                oddLevel += Convert.ToInt32(current.data);
                          
                            //Adds left child to queue
                            if(current.left != null)
                                queue.Enqueue(current.left);
                            //Adds right child to queue
                            if(current.right != null) 
                                queue.Enqueue(current.right);
                             nodesInLevel--;
                        }
                        currentLevel++;
                    }
                    //Calculates difference between oddLevel and evenLevel
                    diffOddEven = Math.Abs(oddLevel - evenLevel);
                }
                return diffOddEven;
            }    
        }
        
        public static void Main()
        {
            DiffOddEven<int> bt = new DiffOddEven<int>();
            //Add nodes to the binary tree
            bt.root = new Node<int>(1);
            bt.root.left = new Node<int>(2);
            bt.root.right = new Node<int>(3);
            bt.root.left.left = new Node<int>(4);
            bt.root.right.left = new Node<int>(5);
            bt.root.right.right = new Node<int>(6);
            
            //Display the difference between sum of odd level and even level nodes
            Console.WriteLine("Difference between sum of odd level and even level nodes: " + bt.difference());                
        }    
    }
}

输出

Difference between sum of odd level and even level nodes: 11

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
    
class DiffOddEven{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //difference() will calculate the difference between sum of odd and even levels of binary tree
    function difference(){
        $oddLevel = 0;
        $evenLevel = 0;
        $diffOddEven = 0;
        
        //Variable nodesInLevel keep tracks of number of nodes in each level
        $nodesInLevel = 0;
          
        //Variable currentLevel keep track of level in binary tree
        $currentLevel = 0;
        
        //queue will be used to keep track of nodes of tree level-wise
        $queue = array();
        
        //Check if root is null
        if($this->root == NULL) {
            print("Tree is empty <br>");
            return 0;
        }
        else {
            //Add root node to queue as it represents the first level
            array_push($queue,$this->root);
            $currentLevel++;
            
            while(sizeof($queue) != 0) {
                
                //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
                $nodesInLevel = sizeof($queue);
                while($nodesInLevel > 0) {
                    $current = array_shift($queue);
                    
                    //Checks if currentLevel is even or not.
                    if($currentLevel % 2 == 0)
                        //If level is even, add nodes's to variable evenLevel
                          $evenLevel += $current->data;
                    else
                        //If level is odd, add nodes's to variable oddLevel
                        $oddLevel += $current->data;
                  
                    //Adds left child to queue
                    if($current->left != NULL)
                        array_push($queue, $current->left);
                    //Adds right child to queue
                    if($current->right != NULL) 
                        array_push($queue, $current->right);
                    $nodesInLevel--;
              }
              $currentLevel++;
          }
          //Calculates difference between oddLevel and evenLevel
          $diffOddEven = abs($oddLevel - $evenLevel);
        }
        return $diffOddEven;
    }    
}    
 
$bt = new DiffOddEven();
//Add nodes to the binary tree
$bt->root = new Node(1);
$bt->root->left = new Node(2);
$bt->root->right = new Node(3);
$bt->root->left->left = new Node(4);
$bt->root->right->left = new Node(5);
$bt->root->right->right = new Node(6);
 
//Display the difference between sum of odd level and even level nodes
print "Difference between sum of odd level and even level nodes: " . $bt->difference();
?>
</body>
</html>

输出

Difference between sum of odd level and even level nodes: 11

下一个主题程序列表

问：计算二叉树奇偶层节点和之差的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问：计算二叉树奇偶层节点和之差的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

从双向链表中删除重复元素的程序

在单向链表末尾插入新节点的程序

打印星型图案 16 的程序

将毫米转换为厘米的程序

打印给定数字的组合 (nCr) 的程序

将厘米转换为毫米的程序

编写计算等腰三角形高（Altitude）的程序

编写查找正八面体（Octahedron）体积的程序

将单链表的最后一个元素与第一个元素交换的程序

删除字符串中所有空格的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器