基本上是围绕着这两题：297. 二叉树的序列化与反序列化 - 力扣（LeetCode） (leetcode-cn.com)和剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode） (leetcode-cn.com)

补充：加入剑指offer32-II 力扣 (leetcode-cn.com)

Leetcode 297:

  1. 序列化部分，需要充分理解队列的使用。
  • 队列用于存储下一层广度优先遍历的节点。
  • 当从队列中取出一个非空节点时，需要同时将该节点的左右子节点放入队列末尾。
  • 从队列中依次取出节点并放在返回的序列（字符串）尾端。
  • 如果当前取出节点为空，则字符串加入“null”以表示空节点。

需要的数据结构：StringBuilder构造字符串，队列存储下一步需要遍历的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String serialize(TreeNode root) {
  if(root == null) return "[]";
  StringBuilder res = new StringBuilder();
  res.append("[");
  Queue<TreeNode> q = new LinkedList<>();
  q.add(root);
  while(!q.isEmpty()) {
    TreeNode cur = q.poll();
    if(cur != null) {
      res.append(cur.val + ",");
      q.add(cur.left);
      q.add(cur.right);
    }
    else res.append("null,");
  }
  res.deleteCharAt(res.length() - 1);
  res.append("]");
  return res.toString();
}
  1. 反序列化部分，首先取括号内的部分分割一下得到字符串数组
  • 队列用来存储需要遍历的节点。和上面一样，队列为空时遍历结束。
  • 先把根节点放入队列，从i=1位置开始遍历字符串数组（根节点的左子节点）。
  • 如果第i项不为null，则字符串数组的第i项作为左子树；i自增后相同规则处理右子树
  • i再自增一次。两次自增与第i项是否为空无关，因此写在条件之外。
  • 左右子树要加入队列以进行下一步遍历。BFS结束后返回根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode deserialize(String data) {
  if(data.equals("[]")) return null;
  String[] strs = data.substring(1, data.length() - 1).split(",");
  Queue<TreeNode> q = new LinkedList<>();
  TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
  q.add(root);
  int i = 1;
  while(!q.isEmpty()) {
    TreeNode cur = q.poll();
    if(!strs[i].equals("null")) {
      cur.left = new TreeNode(Integer.parseInt(strs[i]));
      q.add(cur.left);
    }
    ++i;
    if(!strs[i].equals("null")) {
      cur.right = new TreeNode(Integer.parseInt(strs[i]));
      q.add(cur.right);
    }
    ++i;
  }
  return root;
}

剑指offer32-I：

和上面那题的序列化部分规则差不多，返回结果用数组存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[] {};
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            TreeNode cur = q.poll();
            if(cur.left != null) q.add(cur.left);
            if(cur.right != null) q.add(cur.right);
            res.add(cur.val);
        }
        int[] ans = new int[res.size()];
        for(int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}

剑指offer32-II：

需要按层输出，所以需要使用for循环来设定当前层的循环次数，循环结束后在List<List>中add一个List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
          	List<Integer> tmp = new ArrayList<>();
            int len = q.size();
          	for(int i = 0; i < len; i++) {
                TreeNode cur = q.poll();
              	tmp.add(cur.val);
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
          	res.add(tmp);
        }
        return res;
    }
}