Sword to Offer-32.1 从上往下打印二叉树 ❀❀

19 Apr 2020 in Algorithm

• 题目描述：
  从上往下打印出二叉树的每个结点，同层结点从左至右打印。

解题思路：

二叉树的层次遍历：
1、利用队列保存根节点；
2、只要队列不为空，每出队一个结点，将该结点的左右孩子依次入队（如果存在），从而完成从上到下从，左到右的层次遍历。

问题图解：

AC代码：

// Hierarchical Traversal of Binary Tree

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

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        
        deque.add(root);
        while (!deque.isEmpty()) {
            TreeNode pNode = deque.poll();
            list.add(pNode.val);
            if (pNode.left != null) {
                deque.add(pNode.left);
            }
            if (pNode.right != null) {
                deque.add(pNode.right);
            }
        }
        return list;
    }
}

补充说明：

• 补充： Deque双向队列是Queue单向队列的子类，Deque是抽象类，其实现有ArrayDeque和LinkedList。Deque用法非常灵活：
  1、首先可以用作队列：
  add(e)等效于addLast(e);
  offer(e)等效于offerLast(e);
  remove()等效于removeFirst();
  poll()等效于pollFirst();
  element()等效于getFirst();
  peek()等效于peekFirst()。
  2、实际上还可用作堆栈：
  push(e)等效于addFirst(e);
  pop()等效于removeFirst();
  peek()等效于peekFirst()。

• 这里是牛客编码链接