美文网首页
33_从上到下打印二叉树I

33_从上到下打印二叉树I

作者: 是新来的啊强呀 | 来源:发表于2020-05-26 17:02 被阅读0次

    要求:从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
    思路: 使用二叉树的广度遍历BFS。(广度(层次遍历)优先遍历用队列,深度优先遍历用栈)
    广搜的套路就是用一个队列保存将要搜索的这一层的元素,然后逐个搜索;
    1、将第一个元素加入队列
    2、队列不为空时取队首元素
    3、将下一层元素加入队尾
    4、调到第二步,直到队列为空

    public class L33_PrintFromTopToBottom {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode0 root){
            ArrayList<Integer> list = new ArrayList<>();
            Queue<TreeNode0> qu = new LinkedList<>();
            if(root!=null){
                qu.add(root);
            }else{
                return list;
            }
            while(!qu.isEmpty()){
                TreeNode0 temp = qu.poll();
                list.add(temp.value);
                if(temp.left!=null){
                    qu.add(temp.left);
                }
                if(temp.right!=null){
                    qu.add(temp.right);
                }
            }
            return list;
        }
    }
    

    时间复杂度 O(N) : N 为二叉树的节点数量,即 BFS 需循环 N 次。
    空间复杂度 O(N) : 最差情况下,即当树为平衡二叉树时,最多有 N/2 个树节点同时在 queue 中,使用 O(N) 大小的额外空间。

    相关文章

      网友评论

          本文标题:33_从上到下打印二叉树I

          本文链接:https://www.haomeiwen.com/subject/rmrvahtx.html