每日一题之《剑指offer》59,60,61题

第59题：按之字形顺序打印二叉树

难易度：⭐⭐⭐

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

分析：
准备两个栈，在打印某一层的节点的时候，把下一层的节点保存在相应的栈中。如果打印的当前层数是奇数层则先保存左子节点然后再保存右子节点到第一个栈中，如果打印的当前层数是偶数层，那么就先保存右子节点，然后再保存左子节点到第二个栈中。

代码如下：

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>> list = new ArrayList<>();
        if(pRoot == null){
            return list;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(pRoot);
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            if(!stack1.isEmpty()){
                ArrayList<Integer> arrayList = new ArrayList<>();
                while(!stack1.isEmpty()){
                    TreeNode root = stack1.pop();
                    arrayList.add(root.val);
                    if(root.left != null){
                        stack2.push(root.left);
                    }
                    if(root.right != null){
                        stack2.push(root.right);
                    }
                }
                list.add(arrayList);
            }else{
                ArrayList<Integer> arrayList = new ArrayList<>();
                while(!stack2.isEmpty()){
                    TreeNode root = stack2.pop();
                    arrayList.add(root.val);
                    if(root.right != null){
                        stack1.push(root.right);
                    }
                    if(root.left != null){
                        stack1.push(root.left);
                    }
                }
                list.add(arrayList);
            }
        }
        return list;
    }
}

第60题：把二叉树打印成多行

难易度：⭐⭐⭐

题目描述:
从上到下按层打印二叉树，同一层结点从左至右输出。
每一层输出一行。

解析：和59题是一摸一样的思路，只不过将栈变成了队列而已
代码如下:

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 {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot == null){
            return list;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(pRoot);
        while(!queue1.isEmpty() || !queue2.isEmpty()){
            if(!queue1.isEmpty()){
                ArrayList<Integer> arrayList = new ArrayList<>();
                while(!queue1.isEmpty()){
                    TreeNode root = queue1.poll();
                    arrayList.add(root.val);
                    if(root.left != null){
                        queue2.offer(root.left);
                    }
                    if(root.right != null){
                        queue2.offer(root.right);
                    }
                }
                list.add(arrayList);
            }else{
                ArrayList<Integer> arrayList = new ArrayList<>();
                while(!queue2.isEmpty()){
                    TreeNode root = queue2.poll();
                    arrayList.add(root.val);
                    if(root.left != null){
                        queue1.offer(root.left);
                    }
                    if(root.right != null){
                        queue1.offer(root.right);
                    }
                }
                list.add(arrayList);
            }
        }
        return list;
    }
}

第61题：序列化二叉树

难易度：⭐⭐

题目描述:
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：
把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。
序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改
序列化的结果是一个字符串
序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：
根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

解析：
二叉树的序列化与反序列化是一个同二叉树遍历一样重点的内容，看了代码后并没有什么可以解析的部分，需要达到可以很熟练写出来的程度
代码如下:

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null){
            return "#!";
        }
        String res = root.val + "!";
        res += Serialize(root.left);
        res += Serialize(root.right);
        return res;
  }
    TreeNode Deserialize(String str) {
       String[] strArr = str.split("!");
        Queue<String> queue = new LinkedList<>();
        for(int i = 0;i < strArr.length;i++){
            queue.offer(strArr[i]);
        }
        return deserializeProcess(queue);
  }
    TreeNode deserializeProcess(Queue<String> queue){
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = deserializeProcess(queue);
        head.right = deserializeProcess(queue);
        return head;
    }
}