剑指Offer【从上到下打印二叉树I,II,III】

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1	`[3,9,20,15,7]`

提示：

节点总数 <= 1000

解法

广度优先遍历

class Solution {
    public int[] levelOrder(TreeNode root) {
        //1.特殊判断
        if (root == null) {
            return new int[0];
        }

        //2.利用队列进行bfs
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            res.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        int[] realRes = new int[res.size()];
        for (int i = 0; i < realRes.length; i++) {
            realRes[i] = res.get(i);
        }
        return realRes;
    }
}

时间复杂度：O(n)

来源：力扣（LeetCode）
链接：剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode）

题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示：

节点总数 <= 1000

解法

广度优先遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //返回结果集
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> nodes = new LinkedList<>();
        //特殊判断
        if (root != null) {
            nodes.add(root);
        }
        while (!nodes.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            //分组进行（注意这里的nodes.size会由于nodes.poll而改变大小
            //int i = nodes.size(); i>0   这里 i只会赋值一次
            //int i = 0; i < nodes.size() 这里nodes.size会不断改变
            for (int i = nodes.size(); i > 0; i--) {
                TreeNode node = nodes.poll();
                temp.add(node.val);
                if (node.left != null) {
                    nodes.add(node.left);
                }
                if (node.right != null) {
                    nodes.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

时间复杂度：O(n)

来源：力扣（LeetCode）
链接：剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）

题目描述

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]

提示：

节点总数 <= 1000

解法

广度优先遍历+双端队列

public List<List<Integer>> levelOrder(TreeNode root) {
        //返回结果集
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> nodes = new LinkedList<>();
        //特殊判断
        if (root != null) {
            nodes.add(root);
        }
        while (!nodes.isEmpty()) {
            LinkedList<Integer> temp = new LinkedList<>();
            //分组进行（注意这里的nodes.size会由于nodes.poll而改变大小
            //int i = nodes.size(); i>0   这里 i只会赋值一次
            //int i = 0; i < nodes.size() 这里nodes.size会不断改变
            for (int i = nodes.size(); i > 0; i--) {
                TreeNode node = nodes.poll();
                if (res.size()%2==0){
                    //如果是偶数层就在尾部添加
                    temp.addLast(node.val);
                }else {
                    //如果是在奇数层就在头部添加
                    temp.addFirst(node.val);
                }
                if (node.left != null) {
                    nodes.add(node.left);
                }
                if (node.right != null) {
                    nodes.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }