数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学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
更新日期： 2020 年 5 月 16 日
349 次浏览
广告