点击这里给我发消息【本站不支持IE浏览器】请使用浏览器极速模式浏览本站--效果更佳~!要辅助游戏社区 让游戏简单一点-www.ucxia.com

网站首页 / 精品软件 / 正文

剑指offer面试题牛客_二叉树_把二叉树打印成多行(java版)

2019-07-06 游戏侠 精品软件 122 ℃ 0 评论

welcome to my blog

剑指offer面试题牛客_二叉树_把二叉树打印成多行(java版):

题目描述

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

思路

  • 使用队列这个数据结构, 第一层节点总数是1
  • 先将根节点入队,然后将根节点出队,将根节点的左孩子入队,将根节点的右孩子入队,此时队列里只有第二层的两个节点
  • 将根节点的左孩子出队, 将根节点左孩子的左孩子入队, 将根节点左孩子的右孩子入队
  • 将根节点的右孩子出队, 将根节点右孩子的左孩子入队, 见根节点右孩子的右孩子入队
  • 以此类推, 便能实现从上到下,从左到右打印, 想要实现按层打印, 需要在当前层节点都出队的情况下,统计队列中节点的数量, 此时队列里的节点都是下一层的节点
import java.util.ArrayList;
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> alal = new ArrayList<ArrayList<Integer>>();
        //input check
        if(pRoot == null) 
            return alal;
        //execute
        //ll:节点队列
        LinkedList<TreeNode> ll = new LinkedList<TreeNode>(); //LinkedList实现了Queue接口,可以作为队列使用. 存放节点
        //al:存放当前层的节点的数
        ArrayList<Integer> al = new ArrayList<Integer>(); //存放节点中的数;
        ll.add(pRoot);
        int count=0, total=1;
        TreeNode curr;
        while(!ll.isEmpty()){
            curr = ll.poll();
            count++;
            al.add(curr.val);
            if(curr.left != null) 
                ll.add(curr.left);
            if(curr.right != null)
                ll.add(curr.right);
            if(count == total){
                total = ll.size();
                count = 0;
                alal.add(al);
                al = new ArrayList<Integer>();//遍历完一层之后需要重新申请空间
            }
        }
        return alal;
    }
    
}

递归版

  • 递归函数的逻辑: 将当前节点的val添加到其所在层数对应的ArrayList中,并以此递归调用当前节点的左孩子和右孩子
  • 递归终止条件: 当前节点为null
  • 直接new ArrayList();执行完就用不了了, 但是如果在集合中new一个ArrayList就可以重复调用, 根据索引调用!
  • 这个方法不需要队列, 需要单独标明节点所在的层数
import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        /*
        递归版思路: 在递归函数中加入一个参数,表示节点所在的层数
        递归函数的逻辑: 将当前节点的值放在和层数对应的集合中, 再递归处理当前节点的左孩子和右孩子
        递归终止条件: 当前节点是null
        */
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Core(pRoot, 1, result);
        return result;
    }
    public void Core(TreeNode p, int layer, ArrayList<ArrayList<Integer>> result){
        if(p == null) return;
        if(result.size() < layer)
            result.add(new ArrayList<Integer>());
        result.get(layer-1).add(p.val);
        Core(p.left, layer+1, result);
        Core(p.right, layer+1, result);
    }
}

Tags:

猜你喜欢

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

请填写验证码
«   2020年2月   »
12
3456789
10111213141516
17181920212223
242526272829
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接
  • 订阅本站的 RSS 2.0 新闻聚合

网站公告★客服QQ游戏侠客服×

看片片提示:最新电影资源【少年的你】提供了。
看片片提示:XXX级电影资源【姐妹狂艳】已开放。
看片片提示:最新枪版电影资源【银河补习班】已开放。
辅助更新:皮皮搞笑【决斗英雄】自瞄加速已开放合作--【神仙工具】里有信息
看片片提示:最新枪版电影资源【蜘蛛侠:英雄远征】已开放。
恭喜张先生:预购QQ:52013 + 52014(我爱你一生,我爱你一世) 押金50000元
恭喜王先生:定购QQ:33***(靓号已激活)。 订购金500元已完成
看片片提示:赵哥需要的片片(日本妈妈2)已上架。 请注意观看
恭喜李先生:定购QQ:66***(靓号已激活)。 订购金1100元已完成
恭喜刘先生:定购QQ:520***(靓号已激活)。 订购金3300元已完成
恭喜张女士:定购QQ:888**0 + 888**1(靓号已激活)。 订购金4600元已完成
恭喜孙先生:盗号QQ:77***(盗号已交付)。 订购金5300元已完成
看片片提示:酒哥需要的片片(日本肉肉)已上架。 请注意观看
恭喜马女士,预购QQ:13520 + 13521(一生我爱你情侣号) 押金60000元
恭喜金女士:定购QQ:99***(靓号已激活)。 订购金1300元已完成
看片片提示:胖子需要的片片(金瓶梅)已上架。 请注意观看
看片片提示:三军需要的片片(老师好)已上架。 请注意观看
恭喜樊先生:定购QQ:1988****(生日号已激活)。 订购金200元已完成
恭喜王女士:定购QQ:7878** + 7878**(情侣号已激活)。 订购金3300元已完成
恭喜冯先生:盗号QQ:386****(盗号已交付)。 订购金300元已完成
恭喜刘女士:盗号QQ:999**(盗号已交付)。 订购金6300元已完成
★①:QQ靓号视频仅支持火狐浏览器~★②:承接QQ盗号,先盗号后付款 QQ81801116~★①:需要看片片的留言给我第二天就有了~★②:神仙工具就是游戏辅助(非外挂)各种内部或免费的都 有