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