Java 中二叉树奇数层和偶数层节点之和的差异

javaobject oriented programmingprogramming更新于 2026/1/4 17:48:17

问题陈述

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

示例

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

奇数级节点之和
= 5 + 1 + 4 + 8
= 18
偶数级节点之和
= 2 + 6 + 3 + 7 + 9
= 27
差 = -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));
   }
}