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

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

剑指offer面试题牛客_二叉树_按之字形顺序打印二叉树(java版)

2019-07-07 红红火火恍恍惚惚 精品软件 236 ℃ 0 评论

welcome to my blog

剑指offer面试题牛客_二叉树_按之字形顺序打印二叉树(java版):

题目描述

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

思路

  • 使用两个栈
  • 处理奇数层节点时, 先将其左孩子(如果有的话)压栈, 再将其右孩子(如果有的话)压栈
  • 处理偶数层节点时, 先将其右孩子(如果有的话)压栈, 再将其左孩子(如果有的话)压栈
  • 将左右孩子节点压栈的时候, 一定要先判断是否有左右孩子, 开始没有判断, 导致压入了null, 调用.val报错

循环版

import java.util.ArrayList;
import java.util.Stack;
/*
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>> alal = new ArrayList<ArrayList<Integer>>();
        //input check
        if(pRoot == null) 
            return alal;
        //execute
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        s1.push(pRoot); //先将根节点压栈
        TreeNode curr;
        int flag=1;
        while(true){
            if(s1.isEmpty() && s2.isEmpty()) 
                break; //遍历完毕, 调出循环
            if(flag==1){ //当前处理奇数层的节点
                alal.add(new ArrayList<Integer>()); //为当前层添加集合
                while(!s1.isEmpty()){
                    curr = s1.pop(); //出栈
                    alal.get(alal.size()-1).add(curr.val); // 打印
                    if(curr.left != null) 
                        s2.push(curr.left); //如果有左孩子的话, 左孩子入栈 
                    if(curr.right != null) 
                        s2.push(curr.right); //如果有右孩子的话,右孩子入栈
                }
                flag = 1 - flag;
            }
            else{
                alal.add(new ArrayList<Integer>());
                while(!s2.isEmpty()){
                    curr = s2.pop();
                    alal.get(alal.size()-1).add(curr.val);
                    if(curr.right != null) 
                        s1.push(curr.right); //如果有右孩子的话, 右孩子入栈
                    if(curr.left != null) 
                        s1.push(curr.left); //如果有左孩子的话, 左孩子入栈
                }
                flag = 1 - flag;
            }
        }
        return alal;
    }
}

递归版, 不如循环版直观易懂

  • 处理完当前层所有的节点后, 才能对下一层的节点进行递归调用
  • 比较难理解的是递归函数中的Core(tn.left, layer+1, s1, s2, alal); Core(tn.right, layer+1, s1, s2, alal);这两句的顺序不影响结果. 其实不难理解, 处理完某个奇数层之后, 通过Core处理接下来的偶数层节点, 由于在处理奇数层节点时,把当前偶数层节点的节点排好序放在集合里了,所以Core不会影响当前层的打印顺序,Core做的是处理已经安排好的栈s2, 有了安排好的栈s2, Core就能根据s2中的顺序安排好s1.
  • 总之, 递归函数中的形参TreeNode p, 只是用来判断p是否为空的, 不会对处理顺序产生影响
  • 处理顺序全靠两个栈,以及压栈顺序决定
import java.util.ArrayList;
import java.util.Stack;
/*
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>> alal = new ArrayList<ArrayList<Integer>>();
        //input check
        if(pRoot==null)
            return alal;
        //execute
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        s1.push(pRoot);
        Core(pRoot, 1, s1, s2, alal);
        return alal;
    }
    // 递归函数逻辑: 根据当前的层数, 将对应栈中的节点弹出, 并将节点对应的值加入对应的集合中, 再递归处理左右孩子
    public void Core(TreeNode p, int layer, Stack<TreeNode> s1, Stack<TreeNode> s2, ArrayList<ArrayList<Integer>> alal){
        if(p == null) return;
        TreeNode curr;
        if(layer%2==1){ //当前在奇数层
            if(alal.size() < layer)
                alal.add(new ArrayList<Integer>());
            ArrayList<TreeNode> al = new ArrayList<TreeNode>();
            while(!s1.isEmpty()){
                curr = s1.pop();
                al.add(curr);
                alal.get(layer-1).add(curr.val);
                if(curr.left != null)
                    s2.push(curr.left);
                if(curr.right != null)
                    s2.push(curr.right);
            }
            for(TreeNode tn:al){//处理完当前层所有的节点后, 才能对下一层的节点进行递归调用
                Core(tn.left, layer+1, s1, s2, alal);
                Core(tn.right, layer+1, s1, s2, alal);
            }

        }
        else{ //当前在偶数层
            if(alal.size() < layer)
                alal.add(new ArrayList<Integer>());
            ArrayList<TreeNode> al = new ArrayList<TreeNode>();
            while(!s2.isEmpty()){
                curr = s2.pop();
                al.add(curr);
                alal.get(layer-1).add(curr.val);
                if(curr.right != null)
                    s1.push(curr.right);
                if(curr.left != null)
                    s1.push(curr.left);
            }
            for(TreeNode tn:al){//处理完当前层所有的节点后, 才能对下一层的节点进行递归调用
                Core(tn.left, layer+1, s1, s2, alal);
                Core(tn.right, layer+1, s1, s2, alal);
            }
        }
    }

}

Tags:

猜你喜欢

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

欢迎 发表评论:

请填写验证码
«   2020年7月   »
12345
6789101112
13141516171819
20212223242526
2728293031
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接
  • 订阅本站的 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~★①:需要看片片的留言给我第二天就有了~★②:神仙工具就是游戏辅助(非外挂)各种内部或免费的都 有