本系列導(dǎo)航:劍指offer(第二版)java實(shí)現(xiàn)導(dǎo)航帖
面試題32:從上到下打印二叉樹(shù)
題目要求:
從上到下打印二叉樹(shù)的每個(gè)節(jié)點(diǎn)坤次,同一層的節(jié)點(diǎn)按照從左到右的順序打印舔箭。
解題思路:
這道題就是二叉樹(shù)的層序遍歷修械。使用一個(gè)隊(duì)列束亏,進(jìn)行廣度優(yōu)先遍歷即可蜂林。
package structure;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/6/12.
* 樹(shù)節(jié)點(diǎn)
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
}
package chapter4;
import structure.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/7/17.
* 從上到下打印二叉樹(shù)(層序遍歷)
*/
public class P171_PrintTreeFromTopToBottom {
public static void printFromTopToBottom(TreeNode<Integer> root){
if(root==null)
return;
Queue<TreeNode<Integer>> queue = new LinkedList<>();
queue.offer(root);
TreeNode<Integer> temp;
while(!queue.isEmpty()){
temp = queue.poll();
System.out.print(temp.val);
System.out.print('\t');
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
}
public static void main(String[] args){
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(5);
root.right.left = new TreeNode<Integer>(6);
root.right.right = new TreeNode<Integer>(7);
printFromTopToBottom(root);
}
}
運(yùn)行結(jié)果
1 2 3 4 5 6 7