按深度打印二叉树节点数据

• 2019 年 10 月 5 日
• 筆記

之前去面试，被问到了一个关于二叉树的问题，本身对算法并不擅长，结果想了半天没想出解决方法，经过面试官提点，才恍然大悟，回来后立马把实现写了出来，详见如下。

面试题

题目是这样的，有一个二叉树如下，然后按深度进行打印，应该是1,2,3,4,5,6,7 。

这个一下就能想到是递归，没问题，啪啪啪实现了一通，结果实现出来真实打印出来的却是：1,2,4,5,3,6,7，就实现失败了。后来面试官说将每层的元素都存储起来再递归，回来想了一下就将实现写了出来，详见如下。

代码实现

Node节点类

很简单，没什么好说的。

class Node {      int value;     Node left;     Node right;      public Node(int value, Node left, Node right) {          this.value = value;          this.left = left;          this.right = right;     }  }

主要逻辑方法

实现main方法

    public static void main(String[] args) {          // leaf node         Node node4 = new Node(4, null, null);         Node node5 = new Node(5, null, null);         Node node6 = new Node(6, null, null);         Node node7 = new Node(7, null, null);            // node 2 and node 3         Node node2 = new Node(2, node4, node5);         Node node3 = new Node(3, node6, node7);            // root node         Node root = new Node(1, node2, node3);          List<Node> list = new ArrayList<>();          list.add(root);           printNode(list);     }

执行结果如下

总结

对于二叉树的面试题，一般情况下，都是离不开递归，再想想，每次递归的角色是什么，像我这道题的角色就是每层节点，因为需要按层去打印数据。如果定位到递归角色，再想实现逻辑就好多了。