力扣题102二叉树的层序遍历

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

示例:
二叉树:[3,9,20,null,null,15,7],

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

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

1.用一个队列来存储遍历到的元素。广度优先遍历。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();

        if(root == null){//树为空
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();//用一个队列来存储遍历到的节点
        queue.offer(root);

        while(!queue.isEmpty()){//队列中不为空,表示树未遍历完毕
            List<Integer> subList = new ArrayList<>();
            int size = queue.size();//记录这个层有几个元素

            for(int i =0;i < size;i++){//从队列中取出该层的所有元素,加入subList
                root = queue.poll();
                subList.add(root.val);

                if(root.left != null){//如果当前节点的左子树不为空,将左子节点加入队列
                    queue.offer(root.left);
                }

                if(root.right != null){//如果当前节点的右子树不为空,将右子节点加入队列
                    queue.offer(root.right);
                }
            }

            list.add(subList);
        }

        return list;
    }
}

2.迭代实现,深度优先遍历。

class Solution {
    List<List<Integer>> list = new ArrayList<>();

    //深度优先遍历,把每一个节点加入到对应层的列表中

    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return list;
        }

        levelOrder(root,0);
        return list;
    }
    //level表示层数
    public void levelOrder(TreeNode node,int level){
        if(list.size() == level){//当前层数和list的大小一样,就说明需要一个新的列表来存储当前层元素
            list.add(new ArrayList<Integer>());//新建一个新的subList
        }

        list.get(level).add(node.val);//在当前层的subList中插入元素

        if(node.left != null){//如果左子树不为空, 遍历左子树
            levelOrder(node.left,level+1);
        }

        if(node.right != null){//如果右子树不为空,遍历右子树
            levelOrder(node.right,level+1);
        }
    }
}

题源:力扣

上一篇:102. 二叉树的层序遍历


下一篇:102-二叉树的层序遍历