Java中二叉树的奇数级和偶数级节点之和之间的差

问题陈述

对于给定的二叉树，编写一个程序以查找奇数级和偶数级的节点总数之差。假设根在1级，根的左/右子级在2级，依此类推。

示例

        5
      /   \
      2     6
     /  \     \
    1     4    8
   /    /  \
  3    7    9

Sum of nodes at odd level
= 5 + 1 + 4 + 8
= 18
Sum of nodes at even level
= 2 + 6 + 3 + 7 + 9
= 27
Difference = -9.

解

使用递归遍历。遍历期间，返回根节点及其左，右子节点之差。

示例

以下是Java中的程序，用于查找所需的输出。

class Node {
   int data;
   Node left, right;
   Node(int data){
      this.data = data;
      this.left = this.right = null;
   }
}
public class JavaTester {
   public static Node getTree(){
      Node root = new Node(5);
      root.left = new Node(2);
      root.right = new Node(6);
      root.left.left = new Node(1);
      root.left.right = new Node(4);
      root.left.right.left = new Node(3);
      root.right.right = new Node(8);
      root.right.right.right = new Node(9);
      root.right.right.left = new Node(7);
      return root;
   }
   public static int difference(Node node){
      if(node == null) return 0;
      return node.data - difference(node.left) - difference(node.right);
   }
   public static void main(String args[]){
      Node tree = getTree();
      System.out.println(difference(tree));
   }
}

输出结果

-9