二叉树相关问题解题套路

• 广度优先遍历（BFS：Breath First Search）、深度优先遍历（DFS：Depth First Search），广度优先（按层）遍历用队列，深度优先遍历优先用递归，栈的实现要比递归复杂一些。

注意点

• 换行打印需要两个指针：一个保存当前行的最右节点，一个跟踪下一行最新加入的节点，当当前行最右节点弹出时，更新为下一行最新加入的节点，这一行便可以跟下一行的节点区分开来。
• 之字形打印链表需要三个指针，一个保存当前行在队列中最后弹出的节点，一个保存向右遍历时上一行的最右节点，一个保存向左遍历时上一行的
  最左节点。奇数行队列弹出队头，往队尾添加新节点，先添加左子节点，后添加右子节点；偶数行队列弹出队尾，往队头添加新节点，先添加右子节点，后添加左子节点。

目录

• 从上往下打印二叉树
• 把二叉树打印成多行
• 按之字形顺序打印二叉树（较难，还需要练习）
• 序列化二叉树（不能做到bug free，还需练习）

从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode p = queue.poll();
        res.add(p.val);
        if (p.left != null) {
            queue.add(p.left);
        }
        if (p.right != null) {
            queue.add(p.right);
        }
    }
    return res;
}

把二叉树打印成多行

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

• 二叉树按层打印，必然是用队列实现

ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    if (pRoot == null) {
        res.add(list);
        return res;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(pRoot);
    // last 存放当前行最右节点，nlast保存最新加入队列的节点
    TreeNode last = pRoot, nlast = pRoot;
    while (!queue.isEmpty()) {
        TreeNode p = queue.poll();
        list.add(p);
        if (p.left != null) {
            queue.add(p.left);
            nlast = p.left;
        }
        if (p.right != null) {
            queue.add(p.right);
            nlast = p.right;
        }
        // 当队列弹出的节点跟last节点相同，说明这一行打印完了
        // last更新为nlast，也就是下一行的最右节点
        if (p == last) {
            last = nlast;
            res.add(list);
            list = new ArrayList<>();
        }
    }
    return res;
}

按之字形顺序打印二叉树

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

• 双向链表，奇数层往队尾添加元素，弹出队头；偶数层往队头添加元素，弹出队尾。left监视偶数层是否到达最左边，right监视奇数层是否到达最右边

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    if (pRoot == null) {
        return res;
    }
    LinkedList<TreeNode> queue = new LinkedList();
    queue.add(pRoot);
    boolean leftToRight = true;
    TreeNode left = pRoot, right = pRoot;
    while (!queue.isEmpty()) {
        if (leftToRight) {
            TreeNode p = queue.poll();
            list.add(p.val);
            if (p.left != null) {
                queue.add(p.left);
            }
            if (p.right != null) {
                queue.add(p.right);
            }
            if (p == right) {
                left = queue.peek();
                res.add(list);
                list = new ArrayList<>();
            }
        } else {
            TreeNode p = queue.pollLast();
            list.add(p.val);
            if (p.right != null) {
                queue.addFirst(p.right);
            }
            if (p.left != null) {
                queue.addFirst(p.left);
            }
            if (p == left) {
                right = queue.peekLast();
                res.add(list);
                list = new ArrayList<>();
            }
        }
        leftToRight = !leftToRight;
    }
    return res;
}

序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

• 序列化和反序列化过程如果用递归实现，对于每一个节点都需要不断地将StringBuilder做toString过程，最终其实是每个字符串单独相连接的过程，这个效率是很低的。所以我们选用队列实现

String Serialize(TreeNode root) {
    if (root == null) {
        return "[]";
    }
    StringBuilder sb = new StringBuilder();
    LinkedList<TreeNode> q = new LinkedList<>();
    q.add(root);
    sb.append("[").append(root.val).append(",");
    while (!q.isEmpty()) {
        TreeNode p = q.poll();
        if (p.left != null) {
            sb.append(p.left.val).append(",");
            q.add(p.left);
        } else {
            sb.append("#,");
        }
        if (p.right != null) {
            sb.append(p.right.val).append(",");
            q.add(p.right);
        } else {
            sb.append("#,");
        }
    }
    return sb.deleteCharAt(sb.length() - 1).append("]").toString();
}

TreeNode Deserialize(String str) {
    if (str == null || str.equals("[]")) {
        return null;
    }
    String[] arr = str.substring(1, str.length() - 1).split(",");
    int k = 0, len = arr.length;
    LinkedList<TreeNode> q = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.valueOf(arr[k++]));
    q.add(root);
    while (k < len && !q.isEmpty()) {
        TreeNode p = q.poll();
        if (k < len && !"#".equals(arr[k])) {
            p.left = new TreeNode(Integer.valueOf(arr[k]));
            q.add(p.left);
        }
        k++;
        if (k < len && !"#".equals(arr[k])) {
            p.right = new TreeNode(Integer.valueOf(arr[k]));
            q.add(p.right);
        }
        k++;
    }
    return root;
}