之前去面试,被问到了一个关于二叉树的问题,本身对算法并不擅长,结果想了半天没想出解决方法,经过面试官提点,才恍然大悟,回来后立马把实现写了出来,详见如下。
题目是这样的,有一个二叉树如下,然后按深度进行打印,应该是1,2,3,4,5,6,7 。
这个一下就能想到是递归,没问题,啪啪啪实现了一通,结果实现出来真实打印出来的却是:1,2,4,5,3,6,7,就实现失败了。后来面试官说将每层的元素都存储起来再递归,回来想了一下就将实现写了出来,详见如下。
很简单,没什么好说的。
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;
}
}
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);
}
对于二叉树的面试题,一般情况下,都是离不开递归,再想想,每次递归的角色是什么,像我这道题的角色就是每层节点,因为需要按层去打印数据。如果定位到递归角色,再想实现逻辑就好多了。