内容简介:给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。例如:给定二叉树: [3,9,20,null,null,15,7],
题目
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如:
给定二叉树: [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; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> currentRes = new LinkedList<>(); // 当前队列的大小就是上一层的节点个数, 依次出队 while (size > 0) { TreeNode current = queue.poll(); if (current == null) { continue; } currentRes.add(current.val); // 左子树和右子树入队. if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } size--; } res.add(currentRes); } return res; } }
这道题可不可以用非递归来解呢?
递归的子问题:遍历当前节点, 对于当前层, 遍历左子树的下一层层,遍历右子树的下一层
递归结束条件: 当前层,当前子树节点是null
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } levelOrderHelper(res, root, 0); return res; } /** * @param depth 二叉树的深度 */ private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) { if (root == null) { return; } if (res.size() <= depth) { // 当前层的第一个节点,需要new 一个list来存当前层. res.add(new LinkedList<>()); } // depth 层,把当前节点加入 res.get(depth).add(root.val); // 递归的遍历下一层. levelOrderHelper(res, root.left, depth + 1); levelOrderHelper(res, root.right, depth + 1); } }
热门阅读
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 【Leetcode】103. 二叉树的锯齿形层次遍历
- Leetcode树的层次遍历之PHP解析(102. Binary Tree Level Order Traversal)
- Scala 类型层次结构
- Scala 类型层次结构
- 威胁情报的层次分析
- 值对象的层次结构
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。