二叉树相关问题解题套路
- 广度优先遍历（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;
}
网友评论