從上到下打印二叉樹

從上到下打印出二叉樹的每個(gè)節(jié)點(diǎn)准验，同一層的節(jié)點(diǎn)按照從左到右的順序打印冲茸。

例如:
給定二叉樹: [3,9,20,null,null,15,7],

   3
   / \
  9  20
    /  \
   15   7

返回：

[3,9,20,15,7]

提示：

1. 節(jié)點(diǎn)總數(shù) <= 1000

今日未能解答钾麸。

以下為參考題解所寫的Java代碼寞秃。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public int[] levelOrder(TreeNode root) {
    if (root == null) return new int[0];
    Queue<TreeNode> treeNodes = new LinkedList<TreeNode>(){{add(root);}};
    List<Integer> list = new ArrayList<>();
    while (!treeNodes.isEmpty()) {
      TreeNode treeNode = treeNodes.poll();
      list.add(treeNode.val);
      if (treeNode.left != null) treeNodes.add(treeNode.left);
      if (treeNode.right != null) treeNodes.add(treeNode.right);
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < res.length; i++) {
      res[i] = list.get(i);
    }
    return res;
}

以下為python3代碼：

class Solution:
    def levelOrder(self: TreeNode) -> List[int]:
        if not self: return []
        res, queue = [], collections.deque()
        queue.append(self)
        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res

if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2)
    print(Solution.levelOrder(root))

解題思路：

1. 巧妙的利用了隊(duì)列的特性---先進(jìn)先出适刀，將每個(gè)節(jié)點(diǎn)的非空子節(jié)點(diǎn)從左到右存放到隊(duì)列中穷蛹，并遍歷隊(duì)列土陪。題目要求的二叉樹的 從上至下 打印（即按層打与妊）鬼雀，又稱為二叉樹的 廣度優(yōu)先搜索（BFS）。BFS 通常借助 隊(duì)列 的先入先出特性來實(shí)現(xiàn)蛙吏。
2. 解題思路：
   • 當(dāng)TreeNode為空時(shí)源哩，返回空數(shù)組
   • 將root節(jié)點(diǎn)的TreeNode放入隊(duì)列中，當(dāng)隊(duì)列不為空時(shí)鸦做，獲取隊(duì)列頂端數(shù)據(jù)的值存入數(shù)組中励烦；同時(shí)，將非空左節(jié)點(diǎn)和非空右節(jié)點(diǎn)放入隊(duì)列泼诱。利用隊(duì)列先進(jìn)先出的特性坛掠，實(shí)現(xiàn)獲取每個(gè)節(jié)點(diǎn)的val值。

參考題解來源：leetcode

廣度優(yōu)先搜索（BFS）：寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一治筒，這一算法也是很多重要的圖的算法的原型屉栓。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS耸袜，屬于一種盲目搜尋法系瓢，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果句灌。換句話說夷陋，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖胰锌，直到找到結(jié)果為止骗绕。

BFS，其英文全稱是Breadth First Search资昧。 BFS并不使用經(jīng)驗(yàn)法則算法酬土。從算法的觀點(diǎn)，所有因?yàn)檎归_節(jié)點(diǎn)而得到的子節(jié)點(diǎn)都會(huì)被加進(jìn)一個(gè)先進(jìn)先出的隊(duì)列中格带。一般的實(shí)驗(yàn)里撤缴，其鄰居節(jié)點(diǎn)尚未被檢驗(yàn)過的節(jié)點(diǎn)會(huì)被放置在一個(gè)被稱為 open 的容器中（例如隊(duì)列或是鏈表）刹枉，而被檢驗(yàn)過的節(jié)點(diǎn)則被放置在被稱為 closed 的容器中。

與BFS相對應(yīng)的是深度優(yōu)先算法屈呕，深度優(yōu)先主要依賴與棧來實(shí)現(xiàn)微宝。

深度優(yōu)先和廣度優(yōu)先的對比：