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

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

面试题

题目是这样的,有一个二叉树如下,然后按深度进行打印,应该是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);
   }

执行结果如下

总结

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

觉得有帮助,欢迎关注

原文发布于微信公众号 - 爪哇之路(java_roads)

原文发表时间:2018-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券