正文
简介【 二叉树的层序遍历】【这个二叉树的遍历有一些不同啊,我们一起看看】
题目描述#
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7
返回其层次遍历结果:
[ [3], [9,20], [15,7] ]
我的代码#
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.*; class Solution { TreeNode nullNode = new TreeNode(Integer.MAX_VALUE); public List<List<Integer>> levelOrder(TreeNode root) { ArrayDeque<TreeNode> queue = new ArrayDeque<>(16); List<List<Integer>> returnList = new ArrayList<>(); List<Integer> item = null; if (null != root) { queue.push(root); queue.push(nullNode); while (null != root || !queue.isEmpty()) { TreeNode treeNode = queue.pollLast(); if (null != treeNode && Integer.MAX_VALUE != treeNode.val) { if (null != treeNode.left) { queue.push(treeNode.left); } if (null != treeNode.right) { queue.push(treeNode.right); } if (Integer.MAX_VALUE != treeNode.val) { if(null==item){ item=new ArrayList<>(); } item.add(treeNode.val); } if (!queue.isEmpty()) { TreeNode last = queue.getLast(); if (null != last && last.val == Integer.MAX_VALUE) { queue.pollLast(); queue.push(nullNode); returnList.add(item); item=null; } } }else { root=null; } } } return returnList; } }
运行结果#