來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

題目描述

給你一個(gè)二叉樹(shù)铃将，請(qǐng)你返回其按 層序遍歷 得到的節(jié)點(diǎn)值迫悠。 （即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）廊营。
【 二叉樹(shù)的后序遍歷節(jié)點(diǎn)訪問(wèn)順序：左節(jié)點(diǎn)、右節(jié)點(diǎn)霜运、根節(jié)點(diǎn)】
【二叉樹(shù)的中序遍歷節(jié)點(diǎn)訪問(wèn)順序：左節(jié)點(diǎn)勾邦、根節(jié)點(diǎn)、右節(jié)點(diǎn)】
【二叉樹(shù)的前序遍歷節(jié)點(diǎn)訪問(wèn)順序：根節(jié)點(diǎn)午衰、左節(jié)點(diǎn)立宜、右節(jié)點(diǎn)】

題目分析

提供兩種方法實(shí)現(xiàn)：

• BFS（Breath First Search）廣度優(yōu)先搜索【推薦使用】
• DFS（Deep First Search）深度優(yōu)先搜索

代碼實(shí)現(xiàn)

public class LevelOrder {


    public static void main(String[] args) {
        LevelOrder preOrder = new LevelOrder();
        /**
         *         1
         *    10      2
         *           3  9
         */
        TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9)));
//        TreeNode root = null;
        preOrder.levelOrder2(root);
        preOrder.levelOrder(root);
    }


    /**
     * 隊(duì)列
     * BFS（Breath First Search）廣度優(yōu)先搜索
     * queue.offer(root); 末尾追加元素
     * queue.peek(); 隊(duì)首出隊(duì)
     * queue.poll(); 獲取隊(duì)首元素
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> subList = new ArrayList<Integer>();
            int currSize = queue.size();
            for (int i = 0; i < currSize; i++) {
                TreeNode currNode = queue.poll();
                subList.add(currNode.val);
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                }
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
            result.add(subList);
        }
        System.out.println(result);
        return result;
    }


    /**
     * DFS（Deep First Search）深度優(yōu)先搜索
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        order(root, result, 0);
        System.out.println(result);
        return result;
    }

    private void order(TreeNode root, List<List<Integer>> list, int level) {
        if (root == null) {
            return;
        }
        if (level >= list.size()) {
            list.add(new ArrayList<Integer>());
        }
        list.get(level).add(root.val);
        order(root.left, list, level + 1);
        order(root.right, list, level + 1);
    }


}

BFS復(fù)雜度

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

好了，今天就到這里臊岸，感謝各位看官到這里橙数，不如點(diǎn)個(gè)關(guān)注吧！