剑指offer—二叉树的层次遍历 解答

剑指offer—二叉树的层次遍历

题目描述

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

思路 —队列

队列拥有先进先出的性质,我们可以逐层对节点进行入队,出队的时候添加到list中,并把它的左右节点入队

  1. 1入队
  2. 1出队,添加到集合,并依次把左右子节点2、3入队
  3. 2出队,添加到集合,并依次把左右子节点5、6入队
  4. 3出队,添加到集合,没有子节点,不添加
  5. 5出队,添加到集合
  6. 6出队,添加到集合

代码

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            list.add(node.val);
            if(node.left!=null)
                q.add(node.left);
            if(node.right!=null)
                q.add(node.right);
        }
        return list;
    }
}

拓展—按层次输出

LeetCode102

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

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

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果:

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

思路

  • 相比上面的题目,该题目的难点在于如何把每层的节点按层次输出

我们分析入队出队情况:

每次循环添加的节点都是一个层次的,每次循环把同一层的元素全部处理

  • 每次循环都会判断并添加子节点
    1. 1节点入队,当前队列长为1,它为一个层次,将它出队
    2. 1节点出队后将添加2个节点,当前队列有两个节点,这两个节点都是一个层次,先将第一个元素2出队
    3. 2出队后将添加两个节点,当前队列有三个节点,这三个节点中3是第二层,要等到3出队后剩下的才是一个层次

这么一看,我们1节点入队后,队列长1,出队后,1为单独一个层次;2入队后,队列长2,循环2次出队两个元素后,这两个元素为一个层次;此时队列只剩下5,6,队列长2,循环两次出队两个元素后,这两个为下一层次

具体过程如下:

  • 创建一个空列表,存储一层数据
  • 计算当前层有多少个元素:等于队列的长度
  • 将这些元素从队列中弹出,并加入空队列中
  • 将他们的孩子节点作为下一层压入队列中
  • 把空队列加入输出集合
  • while循环进入下一层

时间复杂度:O(N) 每个元素遍历一次

空间复杂度:O(N) 列表一个N个元素

代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> l1 = null;
        if(root==null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            l1 = new ArrayList<>();
            for(int i=q.size();i>0;i--){
                TreeNode node = q.poll();
                l1.add(node.val);
                if(node.left!=null)
                    q.add(node.left);
                if(node.right!=null)
                    q.add(node.right);
            }
            list.add(l1);
        }
        return list;
    }
}
  • 递归法

dfs本身无法解决层次遍历,但是如果是在对应位置添加元素,那么就可以使用递归dfs,利用递归参数height深度来添加元素

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

    public void digui(TreeNode node , int height){
        if(result.isEmpty()||result.size()<height+1){
            result.add(new ArrayList<>());
        }
        result.get(height).add(node.val);
        if(node.left!=null){
            digui(node.left, height+1);
        }
        if(node.right!=null){
            digui(node.right, height+1);
        }
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/bfs-btree.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!