对于给定的二叉树,编写一个程序以查找奇数位置和偶数位置的节点总和之差。假设根位于0级,奇数位置,根的左/右子级位于2级,左子级位于奇数位置,右子级位于偶数位置,依此类推。
5 / \ 2 6 / \ \ 1 4 8 / / \ 3 7 9 Sum of nodes at odd positions = 5 + 2 + (1 + 8) + (3 + 9) = 5 + 2 + 9 + 12 = 28 Sum of nodes at even level = 0 + 6 + 4 + 7 = 17 Difference = 11.
使用级别顺序遍历。在遍历期间,将第一个元素标记为奇数位置,然后在遇到新元素时切换到偶数位置,然后再打开下一个,依此类推。
以下是Java中的程序,用于查找所需的输出。
import java.util.LinkedList; 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(LinkedList<Node> queue){ if(queue.isEmpty()) return 0; int evenSum = 0; int oddSum = 0; while(true){ int nodes = queue.size(); if(nodes == 0) break; boolean isOdd = true; while(nodes > 0){ Node node = queue.peek(); if(isOdd) oddSum += node.data; else evenSum += node.data; queue.remove(); nodes--; if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); isOdd = !isOdd; } } return oddSum - evenSum; } public static void main(String args[]){ Node tree = getTree(); LinkedList<Node> queue = new LinkedList<Node>(); queue.add(tree); System.out.println(difference(queue)); } }
输出结果
11