摘要:题目要求对于一棵树进行序遍历。水平遍历即遍历结束当前行以后再遍历下一行,并将每行的结果按行填入到数组中返回。利用水平遍历的话,我们只需要知道当前元素在树中的高度就可以知道应当插入到那个数组中。
题目要求
Given a binary tree, return the level order traversal of its nodes" values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ]
对于一棵树进行level序遍历。水平遍历即遍历结束当前行以后再遍历下一行,并将每行的结果按行填入到数组中返回。
递归这道题还是很基础的啦。利用水平遍历的话,我们只需要知道当前元素在树中的高度就可以知道应当插入到那个数组中。
public List使用队列> levelOrder(TreeNode root) { List
> result = new ArrayList
>(); levelOrder(root, 0, result); return result; } public void levelOrder(TreeNode treeNode, int height, List
> result){ if(treeNode == null) return; if(height>result.size()-1){ result.add(new ArrayList
()); } result.get(height).add(treeNode.val); levelOrder(treeNode.left, height+1, result); levelOrder(treeNode.right, height+1, result); }
其实在数据结构的教材中为了说明栈和队列的使用,分别举的就是中序遍历和水平遍历的例子。在这里我们同样可以使用队列的先进先出的机制将同一行的元素读入后,再逐个读出,并在同时插入下一行中的元素。
public List> levelOrder2(TreeNode root){ List
> result = new ArrayList
>(); if(root==null)return result; Queue
queue = new LinkedList (); queue.offer(root); while(!queue.isEmpty()){ int levNum = queue.size(); List temp = new ArrayList (); for(int i = 0 ; i
想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/71144.html
102. 二叉树的层次遍历 题目描述 给定一个二叉树,返回其按层次遍历的节点值。 (即zhucengde,从左到右访问)。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其层次遍历结果为: [ [3], [9,20], [15,7] ] class Solution: def le...
429. N-ary Tree Level Order Traversal Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example, given a 3-ary tree:showImg(https...
摘要:解题思路层次遍历二叉树,我们采用队列,本题的注意点是需要分割出每一层的序列,所以在从队列中取元素之前,我们要先记录队列的大小,以表示这一层中节点的个数。 Binary Tree Level Order TraversalGiven a binary tree, return the level order traversal of its nodes values. (ie, from...
摘要:栈迭代复杂度时间空间递归栈空间对于二叉树思路用迭代法做深度优先搜索的技巧就是使用一个显式声明的存储遍历到节点,替代递归中的进程栈,实际上空间复杂度还是一样的。对于先序遍历,我们出栈顶节点,记录它的值,然后将它的左右子节点入栈,以此类推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...
Problem Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / ...
阅读 3486·2021-11-12 10:36
阅读 2857·2021-09-22 15:35
阅读 2807·2021-09-04 16:41
阅读 1163·2019-08-30 15:55
阅读 3574·2019-08-29 18:43
阅读 2070·2019-08-23 18:24
阅读 1412·2019-08-23 18:10
阅读 1921·2019-08-23 11:31