剑指 Offer 32 – III. 从上到下打印二叉树

本问题对应的 leetcode 原文链接:剑指 Offer 32 – III. 从上到下打印二叉树
本次对应打卡任务:【二叉树专题】多次考察真题:剑指 Offer 32 – III. 从上到下打印二叉树

问题描述

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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

提示:

  1. 节点总数 <= 1000

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        int sum = 1;
        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = 0; i < k; i++){
                TreeNode t = queue.poll();
                if(sum % 2 = = 1){
                    tmp.add(t.val);
                } else {
                    tmp.addFirst(t.val);
                }

                if(t.left != null) queue.add(t.left);
                if(t.right != null) queue.add(t.right);
            }
            res.add(tmp);
            sum ++;
        }

        return res;
    }
}

时间复杂度:O(n)
额外空间复杂度:容器里最对存放 1/2 的节点,故为 O(n)

发表回复

后才能评论

评论(4)

  • 永久会员 2023年3月10日 下午4:01

    1

  • Gg 普通 2022年12月31日 下午11:13
    // 层序遍历
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if(root == null){
                return res;
            }
            Deque<TreeNode> dq = new ArrayDeque<>();
            dq.offerLast(root);
            boolean reverse = false;
            while(!dq.isEmpty()){
                int size = dq.size();
                List<Integer> currList = new ArrayList<>();
                for(int i = 0; i < size; i++){
                    TreeNode curr = dq.pollFirst();
                    currList.add(curr.val);
                    if(curr.left != null){
                        dq.offerLast(curr.left);
                    }
                    if(curr.right != null){
                        dq.offerLast(curr.right);
                    }
                }
                if(reverse){
                    Collections.reverse(currList);
                }
                reverse = reverse == true ? false : true;
                res.add(currList);
            }
            return res;
        }
    }
    
  • 优秀市民 普通 2022年11月1日 下午4:32
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null) queue.add(root);
            while(!queue.isEmpty()){
                LinkedList<Integer> tmp = new LinkedList<>();
                for(int i  = queue.size(); i > 0;i--){
                    TreeNode node = queue.poll();
                    //偶数层 队列头部
                    if(res.size() % 2 == 0){
                        tmp.addLast(node.val);
                    }
                    //奇数层
                    else {
                        tmp.addFirst(node.val);
                    }
                    if(node.left != null) {
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
                res.add(tmp);
            }
            return res;
    
        }
    }
    

    使用双端队列,用res来判断偶数奇数层,偶数层是从尾部出队,奇数层时从头部出队
    时间复杂度on

  • 訁訁訁訁訁 永久会员 2022年10月30日 下午9:15

    使用Collections偶数行反转?(学的)

    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> ret = new ArrayList<>();
            if(root == null) return ret;
            queue.offer(root);
            while(!queue.isEmpty()){
                List<Integer> list = new ArrayList<>();
                int size = queue.size();
                for(int i = 0;i < size;i++){
                    TreeNode cur = queue.poll();
                    list.add(cur.val);
                    if(cur.left != null) queue.offer(cur.left);
                    if(cur.right != null) queue.offer(cur.right);
                }
                ret.add(list);
            }
            for(int i=1;i<ret.size();i+=2){
                Collections.reverse(ret.get(i));
            }
            return ret;
        }
    }
    

    使用LinkedList特性模拟双端队列

    时间复杂度 O(N) : N 为二叉树的节点数量,即 BFS 需循环 N 次,占用 O(N) ;双端队列的队首和队尾的添加和删除操作的时间复杂度均为 O(1)
    空间复杂度 O(N) : 最差情况下,即当树为满二叉树时,最多有 N/2 个树节点 同时 在 deque 中,使用 O(N) 大小的额外空间。

    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> ret = new ArrayList<>();
            if(root == null) return ret;
            queue.offer(root);
            int depth = 1;
            while(!queue.isEmpty()){
                LinkedList<Integer> list = new LinkedList<>();
                int size = queue.size();
                for(int i = 0;i < size;i++){
                    TreeNode cur = queue.poll();
                    if(depth % 2 == 1){
                        //奇数
                        list.add(cur.val);
                    }else{
                        //偶数前插
                        list.addFirst(cur.val);
                    }
                    if(cur.left != null) queue.offer(cur.left);
                    if(cur.right != null) queue.offer(cur.right);
                }
                depth++;
                ret.add(list);
            }
            return ret;
        }
    }
    

    优化,一次循环奇数偶数层同时进行

    奇数层:从左向右打印,先左后右加入下层节点

    偶数层:从右向左打印,先右后左加入下层节点

    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            Deque<TreeNode> deque = new LinkedList<>();
            List<List<Integer>> ret = new ArrayList<>();
            if(root == null) return ret;
            deque.add(root);
            while(!deque.isEmpty()){
                List<Integer> list = new ArrayList<>();
    
                for(int i = deque.size();i > 0;i--){
                    TreeNode cur = deque.removeFirst();
                    list.add(cur.val);
                    //先左后右加入下层节点
                    if(cur.left != null) deque.addLast(cur.left);
                    if(cur.right != null) deque.addLast(cur.right);
                }
                ret.add(list);
                if(deque.size() == 0) break;
                list = new ArrayList<>();
                for(int i = deque.size();i > 0;i--){
                    TreeNode cur = deque.removeLast();
                    list.add(cur.val);
                    // 先右后左加入下层节点
                    if(cur.right != null) deque.addFirst(cur.right);
                    if(cur.left != null) deque.addFirst(cur.left);
                }
                ret.add(list);
            }
            return ret;
        }
    }