编程实现：《直通BAT面试算法精讲课》第一课：二叉树按层遍历

题目描述：给定一棵二叉树头节点root，按照层次打印二叉树，并要求携带行号的相关信息（例如一层遍历完后要求打印换行符或者每一层都打印行号）。

要求设计算法，按照以下格式打印出该二叉树：

1.首先我们要理解按层遍历，按层遍历主要针对图的宽度优先遍历（DFS），而宽度优先遍历通常又使用队列结构。

2.为什么会用队列呢？这跟队列的特性有关，因为队列是先进先出，因此先进入的结点就可以先被弹出。

【思路】：

我们只需准备两个指针，last：表示正在打印的当前行的最右结点

nlast：表示下一行的最右结点。它始终记录刚进入队列的结点，一直记录目前下一层最右的结点。

如果每一层都做宽度优先遍历，当遍历到last时，说明这一层已经打印完了，此时将last指向下一层的最右结点即，让last=nlast，就可以进行下一行的遍历了，直到所有结点都打印完。那么要如何去正确的更新last和nlast呢?

只要让nlast一直跟踪记录宽度优先遍历最新加入队列的结点即可，因为最新加入的队列节点一定是目前发现的下一行的最右节点，所以在当前行打印完时，nlast一定是下一行所有节点中最右的节点。

【准备】

接下来我们需要准备什么呢？因为我们是对树进行操作，所以我们首先先来定义树

public class TreeNode(){
   int x= 0;//结点的值
   TreeNode left = null;//左子树
   TreeNode right = null;//右子树
   public TreeNode(int x){
    this.x = x;
}
}

，需要用到队列，所以我们需要创建一个队列

//创建一个队列，使用链表LinkedList实现队列
LinkedList <TreeNode>queue = new LinkedLst<>();

接下来我们需要有集合来存放遍历过的结点，每一个集合存放每一层遍历过的结点，而最终的结果也是一个集合，该集合包含了刚刚所遍历的每一个集合，所以我们定义集合

ArrayList<ArrayList<TreeNode>>result = new ArrayList<>();


//主要代码  public int run(TreeNode root){         TreeNode nlast = null;    //当前正在访问的结点,遍历访问，每遍历一个，就将它存放在队列中，继续指向下一个结点     TreeNode last = root;//当前行的最后一个结点     TreeNode temp;//临时存放弹出来的结点     LinkedList<TreeNode>queue = new LinkedList();//队列     

//将根结点放到队列中
queue.add(root);
/******开始循环********/
while(queue.size()!=0){
/*===1、弹出操作===*/
temp = queue.poll();
System.out.print(temp+" ");
/*===2、放入左右子树===*/
if(temp.left!=null){nlast = temp.left;queue.add(temp.left)};//注意是正在访问(被弹出)的结点的左右子树
if(temp.right!=null){nlast = temp.right;queue.add(temp.right)};
/*===3、判断===*/
if(temp == last){
System.out.print("\n");
last = nlast;
}
}
 }

秒客网

编程实现：《直通BAT面试算法精讲课》第一课：二叉树按层遍历

相关文章