剑指offer-从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

这道题实质是考查树的遍历算法。从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点， 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。

import java.util.Deque;
import java.util.LinkedList;

public class Test {
    
    class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value) {
            this.value = value;
        }
    }
    
    public void printFromTopToBottom(TreeNode root) {
        if(root == null) return;
        Deque<TreeNode> dequeNode = new LinkedList<TreeNode>();
        // 根结点入队
        dequeNode.add(root);
        
        while(dequeNode.size() != 0) {
            // 队首结点出队列
            TreeNode node = dequeNode.pop();
            
            System.out.print(node.value + " ");
            // 如果左子结点不为空，则左子结点入队
            if(node.left != null)
                dequeNode.add(node.left);
            // 如果右子结点不为空，则右子结点入队
            if(node.right != null) 
                dequeNode.add(node.right);
        }
    }
    
    public static void main(String[] args) {
        Test t = new Test();
        TreeNode node1 = t.new TreeNode(1);
        TreeNode node2 = t.new TreeNode(2);
        TreeNode node3 = t.new TreeNode(3);
        TreeNode node4 = t.new TreeNode(4);
        TreeNode node5 = t.new TreeNode(5);
        TreeNode node6 = t.new TreeNode(6);
        TreeNode node7 = t.new TreeNode(7);
        
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        
        t.printFromTopToBottom(node1);  
    }
}