JZ59:按之字形顺序打印二叉树

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

使用链表的辅助空间来实现,利用链表的反向迭实现逆序输出

解法1:增加两个TreeNode:last和nlast
last:表示当前遍历层最右结点
nlast:表示下一层最右结点
遍历时,每次将nlast指向插入队列元素,最后一个插入结点时即最右结点。插入左右孩子之后,检测last是否为当前输出结点,若是,则表示需要进行换行,并将last指向下一层的nlast。

import java.util.ArrayList;
import java.util.Queue;
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 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(pRoot);
        TreeNode last=pRoot;
        TreeNode nlast=pRoot;
        boolean flag=true;
        ArrayList<Integer> res=new ArrayList<Integer>();
        while(!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            res.add(tmp.val);

            if(tmp.left!=null){
                queue.add(tmp.left);
                nlast=tmp.left;
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
                nlast=tmp.right;
            }
            if(tmp==last){
                list.add(reverse(res,flag));
                flag=!flag;
                last=nlast;
                res=new ArrayList<Integer>();
            }
        }
        return list;
    }
    public ArrayList<Integer> reverse(ArrayList<Integer> list,boolean flag){
        if(flag==false){
            ArrayList<Integer> res=new ArrayList<Integer>();
            for(int i=list.size()-1;i>=0;i--){
                res.add(list.get(i));
            }
            return res;
        }
        else{
            return list;
        }
    }
} 

解法2:

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;
    }

代码2:

import java.util.ArrayList;
import java.util.Queue;
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 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(pRoot);
        int depth=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            ArrayList<Integer> list=new ArrayList<Integer>();
            for(int i=0;i<size;i++){
                TreeNode tmp=queue.poll();
                list.add(tmp.val);
                if(tmp.left!=null){
                    queue.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                }
            }
            depth++;
            if(depth%2==1){
                res.add(list);
            }
            else{
                res.add(reverse(list));
            }
        }
        return res;
    }
    public ArrayList<Integer> reverse(ArrayList<Integer> list){
        ArrayList<Integer> res=new ArrayList<Integer>();
        for(int i=list.size()-1;i>=0;i--){
            res.add(list.get(i));
        }
        return res;
    }
}

利用两个栈的辅助空间分别存储奇数偶数层的节点,然后打印输出。

import java.util.Stack;
public ArrayList<ArrayList<Integer>> ZiZapPrint(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();

        if(pRoot==null){
            return res;
        }

        Stack<TreeNode> stack1=new Stack<TreeNode>();
        Stack<TreeNode> stack2=new Stack<TreeNode>();

        stack1.push(pRoot);
        int level=1;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            if(level%2==1){
                ArrayList<Integer> list=new ArrayList<Integer>();
                while(!stack1.isEmpty()){
                    TreeNode node=stack1.pop();
                    if(node!=null){
                        list.add(node.value);//把结点值加到list
                        stack2.push(node.left);//因为偶数层,先右后左,所以栈里先放左子树
                        stack2.push(node.right);
                    }
                }
                if(!list.isEmpty()){
                    res.add(list);
                    level++;
                }
            }
            else{
                ArrayList<Integer> list=new ArrayList<Integer>();
                while(!stack2.isEmpty()){
                    TreeNode node=stack2.pop();
                    if(node!=null){
                        list.add(node.value);//把结点值加到list
                        stack1.push(node.right);//因为奇数层,先左后右,所以栈里先放右子树
                        stack1.push(node.left);
                    }
                }
                if(!list.isEmpty()){
                    res.add(list);//偶数层的结点加到res
                    level++;
                }
            }
        }
        return res;
    }
剑指Offer题解 文章被收录于专栏

剑指Offer-Java版本题解

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 14:39
门头沟学院_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-24 07:19
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议