本文共 1452 字,大约阅读时间需要 4 分钟。
题目描述:
从上往下打印二叉树的每个结点,同一层的结点按照从左到右的顺序打印。
思路:
1.循环+队列 每次扫描本层的所有节点放入队列 再从队头读取一个节点继续遍历子节点
public static void printByLoop(BinaryTreeNode root) { Queuequeue = new LinkedBlockingQueue<>(); if (root == null) { //如果二叉树为空 return; } while (root != null) { System.out.print(root.value + " "); if (root.leftNode != null) { queue.add(root.leftNode); } if (root.rightNode != null) { queue.add(root.rightNode); } root = queue.poll(); } }
2.递归实现 必须先计算出树的高度 再打印每层的节点
public static void printByRecursion(BinaryTreeNode root) { if (root == null) { return; } int dep = depth(root); for (int i = 1; i <=dep; i++) { print(root, i); } } private static void print(BinaryTreeNode root, int level) { if (root == null || level < 1) { return; } if (level == 1) { System.out.print(root.value + " "); } print(root.leftNode, level - 1); print(root.rightNode, level - 1); } private static int depth(BinaryTreeNode root) { if (root == null) { return 0; } //计算左右子树的高度 int left = depth(root.leftNode); int right = depth(root.rightNode); if (left > right) { return left + 1; } else { return right + 1; } }
转载地址:http://nhqli.baihongyu.com/