计算二叉树奇数层和偶数层节点和之差的 Java 程序

2025年3月17日 | 阅读 3 分钟

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

Java Program to calculate the Difference between the Sum of the Odd Level and the 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 属性。
- Root 表示树的根节点，初始值为 null。

a. difference() 方法将计算奇数层节点之和与偶数层节点之和之间的差值。

使用队列逐层遍历二叉树。
使用 currentLevel 变量跟踪当前层。
如果 currentLevel 可以被 2 整除，则将 currentLevel 中所有节点的值加到 evenLevel 变量中。否则，将所有节点的值加到 oddLevel 变量中。
通过从 oddLevel 中减去 evenLevel 中的值来计算差值。

程序

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

下一个主题Java 程序

计算二叉树奇数层和偶数层节点和之差的 Java 程序

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

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

Java 程序

计算二叉树奇数层和偶数层节点和之差的 Java 程序

算法

程序

相关帖子

如何在 Java 中将 int 转换为 double

Java 搜索二叉树中节点的程序

判断给定字符串是否为回文的 Java 程序

Java 中将二进制矩阵转换为零矩阵的最小翻转次数

Java 中的回文程序

在控制台上打印以下图案的 Java 程序 6

查找数组中每个元素出现频率的 Java 程序

Java 创建和显示单链表的程序

检查一个字符串是否是另一个字符串旋转的 Java 程序

Java Program to Find Sum of Natural Numbers

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器