Java計算二叉樹每一層的和是一個很有趣的問題,可以通過編程來解決。
public class BinaryTree { private Node root; private static class Node { int value; Node left; Node right; Node(int value) { this.value = value; } } // 計算二叉樹每一層的和 public ListcalculateLevelSum() { List results = new ArrayList<>(); Queue queue = new LinkedList<>(); if (root != null) { queue.offer(root); } while (!queue.isEmpty()) { int size = queue.size(); int sum = 0; for (int i = 0; i< size; i++) { Node node = queue.poll(); sum += node.value; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } results.add(sum); } return results; } }
在上面的代碼中,我們定義了一個二叉樹節點類Node,以及一個BinaryTree類,其中,calculateLevelSum方法可以計算二叉樹每一層的和。該方法使用了一個隊列,每次將一個節點的值加到sum中,然后將該節點的左右節點插入隊列中,直到隊列為空。
我們可以通過以下代碼來測試上述方法:
public class Main { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); binaryTree.root = new BinaryTree.Node(1); binaryTree.root.left = new BinaryTree.Node(2); binaryTree.root.right = new BinaryTree.Node(3); binaryTree.root.left.left = new BinaryTree.Node(4); binaryTree.root.left.right = new BinaryTree.Node(5); binaryTree.root.right.left = new BinaryTree.Node(6); binaryTree.root.right.right = new BinaryTree.Node(7); Listresults = binaryTree.calculateLevelSum(); System.out.println(results); } }
上述測試代碼生成了一顆二叉樹,調用了BinaryTree類的calculateLevelSum方法,并輸出結果,我們可以得到一個包含每層和的列表。運行結果為:[1, 5, 21]