面试算法：利用链表层级打印二叉树节点

57 阅读 0 评论 38 点赞

我是靠谱客的博主善良奇异果，最近开发中收集的这篇文章主要介绍面试算法：利用链表层级打印二叉树节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

更详细的讲解和代码调试演示过程，请参看视频
如何进入google,算法面试技能全面提升指南

给定一个排序二叉树如下：
这里写图片描述

二叉树节点的变量有三种方法，分别是前序遍历，中序遍历，后续遍历。现在，要求我们实现算法，使得逐层将节点打印出来，例如开始先打印最高层，也就是节点5，然后打印第二层，也就是节点3， 7，接着打印第三层，也即是节点1，4，6，8；最后打印最底层，也就是节点0， 2， 9.

这个问题处理不难，我们依赖队列这个数据结构可方便实现这个功能。做法是，

1，首先把根节点加入队列：

2，接着把队列头结点的数值打印出来，把头结点的左右孩子加入队列

5->3->7

3, 去掉队列头结点，然后进入步骤2.

根据上面步骤，算法对节点的处理如下
list: 5
output: 5

list: 3->7
output: 3

list: 7->1->4
output: 7

list: 1->4->6->8
output: 1

list: 4->6->8->0->2
output: 4

list: 6->8->0->2
output: 6

list: 8->0->2
output: 8

list: 0->2->9
output: 0

list: 2->9
output: 2

list: 9
output: 9

对应的代码实现如下：

public class ListUtility {
private Node tail;
private Node head;
private int listLen = 0;
private int postingListLen = 0;
HashMap<Integer, PostingNode> map = new HashMap<Integer, PostingNode>();
TreeNode treeHead = null;
public TreeNode createTree() {
int[] a = new int[]{5,7,3,1,2,6,8,4,9,0};
for (int i = 0; i < 10; i++) {
insertTreeNode(a[i]);
}
return treeHead;
}
private void insertTreeNode(int val) {
if (treeHead == null) {
treeHead = new TreeNode();
treeHead.val = val;
treeHead.left = treeHead.right = null;
return;
}
TreeNode node = treeHead;
while (node != null) {
if (node.val > val && node.left
!= null) {
node = node.left;
continue;
}
if (node.val <= val && node.right != null) {
node = node.right;
continue;
}
TreeNode temp = new TreeNode();
temp.val = val;
temp.left = null;
temp.right = null;
if (node.val > val) {
node.left = temp;
break;
} else {
node.right = temp;
break;
}
}
}
...
}

在ListUtility中，通过createTree和insertTreeNode两个函数来构造排序二叉树。createTree会返回树的根节点。

层级打印的逻辑实现在类PrintTreeList:

import java.util.ArrayList;
public class PrintTreeList {
private ArrayList<TreeNode> list = new ArrayList<TreeNode>();
public PrintTreeList(TreeNode head) {
if (head != null) {
list.add(head);
}
}
public void printTree() {
while (list.size() > 0) {
TreeNode t = list.remove(0);
System.out.print(t.val + " ");
if (t.left != null) {
list.add(t.left);
}
if (t.right != null) {
list.add(t.right);
}
}
}
}