目录
使用函数实现
使用双端队列实现
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回其层次遍历结果:文章来源:https://www.toymoban.com/news/detail-677650.html
[ [3], [20,9], [15,7] ]
提示:文章来源地址https://www.toymoban.com/news/detail-677650.html
节点总数 <= 1000
使用函数实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
helper(root,0);
return res;
}
private void helper(TreeNode root,int level){
if(root==null)
return;
if(res.size()==level){
res.add(new ArrayList<>());
}
if(level%2==0){
res.get(level).add(root.val);
}else{
res.get(level).add(0,root.val);
}
helper(root.left,level+1);
helper(root.right,level+1);
}
}
使用双端队列实现
/**
* 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) {
boolean isEven = false;//从1开始,第一行不是偶数
if(root==null) return new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(true){
int size = queue.size();
LinkedList<Integer> item = new LinkedList<>();
for(int i=0;i<size;i++){
root = queue.poll();
if(!isEven) item.addLast(root.val);
else item.addFirst(root.val);
if(root.left!=null) queue.offer(root.left);
if(root.right!=null) queue.offer(root.right);
}
isEven = !isEven;
ans.add(item);
if(queue.isEmpty()) break;
}
return ans;
}
}
到了这里,关于剑指 Offer 32 - III. 从上到下打印二叉树 III的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!