Java教程

每日一题-Day18-之字形打印二叉树

本文主要是介绍每日一题-Day18-之字形打印二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

解题思路

题目解析:给定一颗二叉树,假设根节点为第一层,按照奇数层,从左到右打印,偶数层,从右到左打印

​ 运用队列的思想

将每一层依次装入队列中,获取队列长度,遍历这一层,同时判断这一层是奇数层还是偶数层,运用LinkedList的addFirst方法,将偶数层的结点从右往左打印

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(pRoot);
        int dep = 0;
        while(!q.isEmpty()){
            LinkedList<Integer> list = new LinkedList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode node = q.poll();
                if(dep%2 == 0){
                    list.add(node.val);
                }else{
                    list.addFirst(node.val);
                }
                if(node.left != null)
                    q.add(node.left);
                if(node.right != null)
                    q.add(node.right);
            }
            dep++;
            res.add(new ArrayList(list));
        }
        return res;
    }
}

来源:牛客网
链接:https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13

这篇关于每日一题-Day18-之字形打印二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!