牛客-NC15-求二叉树的层序遍历

方法一：广度优先遍历（自己写的）

思路：使用一个队列nodes来存放当前层遍历的节点，将根节点放到该队列进行while循环。while中要做两件事：（1）首先是将当前层的值存放到新定义的cur中，用于返回。（2）遍历当前层的节点，并判断当前节点的左子树和右子树，将这层所有节点的子节点放到nxt_level列表中，用于下一层的遍历。将nxt_level存放到nodes进行下一层的while循环。

import java.util.*;

/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */

public class Solution {
   
    /** * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
   
                // write code here
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        // 特判
        if (root == null) {
   
            return ret;
        }
        // nodes为队列
        Deque<ArrayList<TreeNode>> nodes = new LinkedList<>();
        ArrayList<TreeNode> tmp = new ArrayList<>();
        tmp.add(root);
        nodes.add(tmp);
        while (nodes.peek().size() != 0) {
   
            ArrayList<Integer> cur = new ArrayList<>();
            ArrayList<TreeNode> cur_level = nodes.pop();
            ArrayList<TreeNode> nxt_level = new ArrayList<>();

            for (TreeNode node : cur_level) {
   
                cur.add(node.val);
                // 判断左子树、右子树
                if (node.left != null) {
   
                    nxt_level.add(node.left);
                }
                if (node.right != null) {
   
                    nxt_level.add(node.right);
                }
            }
            nodes.add(nxt_level);
            ret.add(cur);

        }
        return ret;
    }
}

时间复杂度： O(N), N 表示节点个数，因为每个点进队和出队各一次。
空间复杂度： O(N), N表示节点个数，队列中元素的个数不超过N个。

方法二：广度优先遍历（LeetCode最优解）

思路：方法一队列的声明过于繁琐，方法二代码更加简洁，应该算这道题的最优解了。

import java.util.*;

/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */

public class Solution {
   
    /** * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
   
        // write code here
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        // 特判
        if (root == null) {
   
            return ret;
        }
        // 声明队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
   
            ArrayList<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
   
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
   
                    queue.offer(node.left);
                }
                if (node.right != null) {
   
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }

        return ret;
    }
}

时间复杂度： O(N), N 表示节点个数，因为每个点进队和出队各一次。
空间复杂度： O(N), N表示节点个数，队列中元素的个数不超过N个。
总结：本题是二叉树遍历除前中后序遍历的另一种遍历方式，这四种遍历方式都可以用递归和迭代两种方式实现，这里给出递归解法的连接，最主要就是要使用一个额外的变量来记录当前遍历到哪一层了。详情请看link。