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

1 简介

在此程序中，我们需要计算奇数级上出现的节点总数与偶数级上出现的节点总数之差。假设，如果一棵树包含5个级别，则

Difference = (L1 + L 3 + L5) - (L2 + L4)  

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

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

2 算法思路

• 定义具有三个属性的Node类，分别是：data，left和right。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点后，为节点的数据部分分配一个适当的值，其左，右子级为NULL。
• 定义另一个具有属性根的类。
  • 根表示最初具有空值的树的根节点。
• 使用队列明智遍历二叉树级别。
• 使用变量currentLevel跟踪当前水平。
• 如果currentLevel被2整除，则将currentLevel中存在的节点的所有值添加到变量evenLevel。否则，将节点的所有值添加到变量oddLevel。
• 通过从奇数级减去偶数级中存在的值来计算差值。

3 程序实现

import java.util.LinkedList;    
import java.util.Queue;    
/**
 * 一点教程网： http://www.yiidian.com
 */     
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