102. 二叉树的层序遍历

Problem: 102. 二叉树的层序遍历

解题方法

广度优先搜索:

• 用队列保存需要每一层

• 根节点入队列

    - 遍历 栈不为空

    - node = queue.Deque();

    - 左子树不为空 入队列

    - 右子树不为空 入队列

    - queue.Dequeue(node);

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     public int val;

 *     public TreeNode left;

 *     public TreeNode right;

 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

public class Solution {

    public IList<IList<int>> LevelOrder(TreeNode root) {

        var res = new List<IList<int>>();

        var queue = new Queue<TreeNode>();

        if(root != null) {

            queue.Enqueue(root);

        }

        while(queue.Count != 0) {

            int size = queue.Count;

            List<int> list = new List<int>();

            while(size > 0) {

                var node = queue.Dequeue();

                if(node.left != null) {

                    queue.Enqueue(node.left);

                }

                if(node.right != null) {

                    queue.Enqueue(node.right);

                }

                list.Add(node.val);

                size--;

            }

            res.Add(list);

        }

        return res;

    }

}