資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究二叉樹的奇數位置和偶數位置節點和之間的差異
問題陳述
給定一棵二叉樹，編寫一個程式查詢奇數位置和偶數位置的節點和之間的差異。假設根節點處於 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
更新於： 16 月 5 日，2020
165 次瀏覽
廣告