首页 > itarticle > 二叉树的层次遍历1

二叉树的层次遍历1

admin 1月 23, 2021 0

102. 二叉树的层次遍历

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

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

返回其层次遍历结果：

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

解法：

二叉树的层遍历使用队列，将节点放入队列中，当节点出队时判断该节点的左，右子树是否为空，如果不为空将其放入队列中，本题因为题目要求每次创建一个新的list将每一层的节点添加到list中，size为队列的大小，用来判断队列中的节点是否全部出来。

/**
 * 自上而下层遍历
 * @param root
 */
public List<List<Integer>> cen2(TreeNode root){
    List<List<Integer>> lists=new ArrayList<>();
    if (root==null){
        return lists;
    }
//使用队列
    LinkedList<TreeNode> treeNodes=new LinkedList<>();
    treeNodes.add(root);
    while(!treeNodes.isEmpty()){
        List<Integer> list=new ArrayList<>();
        int size=treeNodes.size();
        for (int i=0;i<size;i++){
            TreeNode n=treeNodes.pop();
            list.add(n.val);
            if (n.l!=null){
                treeNodes.add(n.l);
            }
            if (n.r!=null){
                treeNodes.add(n.r);
            }
        }
        lists.add(list);
    }
    return lists;
}