二叉树的层序遍历
题目描述
题目
算法1思路
二叉树的层序遍历也可看做是广度优先遍历，我们可以设计一个队列，头结点先入队，然后出队，每出队一个结点，就将它左孩子和右孩子（如果存在）加入队列，记录下出队顺序，即为层序遍历。
算法设计
算法设计优化
代码1实现
public static List<List<Integer>> levelOrder1(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
Queue<TreeNode> queue = new LinkedList<>();
HashMap<TreeNode, Integer> levels = new HashMap<>();
queue.add(root);
levels.put(root, 0);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
int level = levels.get(cur);
// 如果此时该层的链表还未创建，则需新建链表
if (ans.size() == level) {
ans.add(new ArrayList<>());
}
ans.get(level).add(cur.val);
if (cur.left != null) {
queue.add(cur.left);
levels.put(cur.left, level + 1);
}
if (cur.right != null) {
queue.add(cur.right);
levels.put(cur.right, level + 1);
}
}
}
return ans;
}
算法2思路
我们用数组来代替队列，每次处理一层的结点，可以不用再分别记录每个结点位于哪一层。首先，头结点入队，每次拿到队列长度size，然后重复弹出元素-加入左孩子-加入右孩子操作size遍。
算法2设计
代码2实现
public static int MAXN = 2001;
// 假设二叉树结点最多有MAXN个
public static TreeNode[] queue = new TreeNode[MAXN];
// l和r限制每一次处理的size个元素
public static int l, r;
public static List<List<Integer>> levelOrder2(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
l = r = 0;
queue[r++] = root;
while (l < r) { // 队列里还有东西
int size = r - l;
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue[l++];
list.add(cur.val);
if (cur.left != null) {
queue[r++] = cur.left;
}
if (cur.right != null) {
queue[r++] = cur.right;
}
}
ans.add(list);
}
}
return ans;
}
二叉树的锯齿形遍历
题目描述
题目
算法思路
我们沿用二叉树层序遍历的队列，收集该层的节点，用left和right指针指明当前层的节点在队列中的范围，然后交替从left向right遍历或者从right向left遍历，之后类似于层序遍历，将队列中left到right范围内每个结点的左右孩子加入队列中，修改left和right指针的位置。
代码实现
// 二叉树的锯齿形层序遍历
public class Code02_ZigzagLevelOrderTraversal {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 提交以下的方法
// 用每次处理一层的优化bfs就非常容易实现
// 如果测试数据量变大了就修改这个值
public static int MAXN = 2001;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
l = r = 0;
queue[r++] = root;
// false 代表从左往右
// true 代表从右往左
boolean reverse = false;
while (l < r) {
int size = r - l;
ArrayList<Integer> list = new ArrayList<Integer>();
// reverse == false, 左 -> 右， l....r-1, 收集size个
// reverse == true, 右 -> 左， r-1....l, 收集size个
// 左 -> 右, i = i + 1
// 右 -> 左, i = i - 1
for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
TreeNode cur = queue[i];
list.add(cur.val);
}
for (int i = 0; i < size; i++) {
TreeNode cur = queue[l++];
if (cur.left != null) {
queue[r++] = cur.left;
}
if (cur.right != null) {
queue[r++] = cur.right;
}
}
ans.add(list);
reverse = !reverse;
}
}
return ans;
}
}
求二叉树的最大特殊宽度
题目描述
题目
算法思路
我们可以将不存在的结点也填补上，将该二叉树看做是完全二叉树，因此我们可以将结点编号，由此计算出孩子结点的编号，某一层编号最大和最小的孩子结点的差值即为二叉树的最大特殊宽度。
思路
代码实现
// 二叉树的最大特殊宽度
public class Code03_WidthOfBinaryTree {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 提交以下的方法
// 用每次处理一层的优化bfs就非常容易实现
// 如果测试数据量变大了就修改这个值
public static int MAXN = 3001;
// 结点队列
public static TreeNode[] nq = new TreeNode[MAXN];
// 编号队列
public static int[] iq = new int[MAXN];
public static int l, r;
public static int widthOfBinaryTree(TreeNode root) {
int ans = 1;
l = r = 0;
nq[r] = root;
iq[r++] = 1;
while (l < r) {
int size = r - l;
ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
for (int i = 0; i < size; i++) {
TreeNode node = nq[l];
int id = iq[l++];
if (node.left != null) {
nq[r] = node.left;
iq[r++] = id * 2;
}
if (node.right != null) {
nq[r] = node.right;
iq[r++] = id * 2 + 1;
}
}
}
return ans;
}
}
二叉树的最大和最小深度
题目描述
示例
如上图，二叉树最大深度为5，最小深度为3，注意计算深度时，必须要到叶节点。
代码实现
// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
public static int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
public int minDepth(TreeNode root) {
if (root == null) {
// 当前的树是空树
return 0;
}
if (root.left == null && root.right == null) {
// 当前root是叶节点
return 1;
}
int ldeep = Integer.MAX_VALUE;
int rdeep = Integer.MAX_VALUE;
if (root.left != null) {
ldeep = minDepth(root.left);
}
if (root.right != null) {
rdeep = minDepth(root.right);
}
return Math.min(ldeep, rdeep) + 1;
}
}
先序遍历的序列化的反序列化
题目描述
示例
中序序列化和反序列化无法确定同一棵二叉树
// 二叉树先序序列化和反序列化
public class Code05_PreorderSerializeAndDeserialize {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v) {
val = v;
}
}
// 提交这个类
public class Codec {
public String serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
f(root, builder);
return builder.toString();
}
void f(TreeNode root, StringBuilder builder) {
if (root == null) {
builder.append("#,");
} else {
builder.append(root.val + ",");
f(root.left, builder);
f(root.right, builder);
}
}
public TreeNode deserialize(String data) {
String[] vals = data.split(",");
cnt = 0;
return g(vals);
}
// 当前数组消费到哪了
public static int cnt;
TreeNode g(String[] vals) {
String cur = vals[cnt++];
if (cur.equals("#")) {
return null;
} else {
TreeNode head = new TreeNode(Integer.valueOf(cur));
head.left = g(vals);
head.right = g(vals);
return head;
}
}
}
}
层序遍历的序列化和反序列化
算法思路
同样借助队列，序列化时，元素依次出队，如果左孩子或者右孩子不为空，则将其入队，并加入序列化字符串；若为空，则只加入序列化字符串。反序列化时，元素出队，左右孩子也去消耗掉去构造建树，再判断左右孩子是否不为空，如果不为空，则入队。
序列化
// 二叉树按层序列化和反序列化
public class Code06_LevelorderSerializeAndDeserialize {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v) {
val = v;
}
}
// 提交这个类
// 按层序列化
public class Codec {
public static int MAXN = 10001;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;
public String serialize(TreeNode root) {
StringBuilder builder = new StringBuilder();
if (root != null) {
builder.append(root.val + ",");
l = 0;
r = 0;
queue[r++] = root;
while (l < r) {
root = queue[l++];
if (root.left != null) {
builder.append(root.left.val + ",");
queue[r++] = root.left;
} else {
builder.append("#,");
}
if (root.right != null) {
builder.append(root.right.val + ",");
queue[r++] = root.right;
} else {
builder.append("#,");
}
}
}
return builder.toString();
}
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}
String[] nodes = data.split(",");
int index = 0;
TreeNode root = generate(nodes[index++]);
l = 0;
r = 0;
queue[r++] = root;
while (l < r) {
TreeNode cur = queue[l++];
cur.left = generate(nodes[index++]);
cur.right = generate(nodes[index++]);
if (cur.left != null) {
queue[r++] = cur.left;
}
if (cur.right != null) {
queue[r++] = cur.right;
}
}
return root;
}
private TreeNode generate(String val) {
return val.equals("#") ? null : new TreeNode(Integer.valueOf(val));
}
}
}
利用先序和中序遍历构造二叉树
题目描述
题目
算法思路
首先，题目表明二叉树的节点没有重复值，因此根据先序遍历和中序遍历我们可以确定唯一一棵二叉树，该二叉树的头结点一定是先序遍历的第一个结点，而头结点的左子树一定是中序遍历中，头结点左边的节点，而右子树一定是头结点右边的节点，同理，就可以递归实现构建二叉树。
import java.util.HashMap;
// 利用先序与中序遍历序列构造二叉树
public class Code07_PreorderInorderBuildBinaryTree {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int v) {
val = v;
}
}
// 提交如下的方法
public static TreeNode buildTree(int[] pre, int[] in) {
if (pre == null || in == null || pre.length != in.length) {
return null;
}
// 用hashmap记录中序遍历某个节点所在的位置
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
map.put(in[i], i);
}
return f(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
}
public static TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {
if (l1 > r1) {
return null;
}
TreeNode head = new TreeNode(pre[l1]);
if (l1 == r1) {
return head;
}
int k = map.get(pre[l1]);
// pre : l1(........)[.......r1]
// in : (l2......)k[........r2]
// (...)是左树对应，[...]是右树的对应
head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
return head;
}
}
验证完全二叉树
算法思路
进行层序遍历，若判断以下两个条件，
1）出现有右无左的结点，则不是完全二叉树
2）若出现孩子不全，则后续遍历的所有结点要均为叶子结点，否则就不是完全二叉树
package class036;
// 验证完全二叉树
public class Code08_CompletenessOfBinaryTree {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 提交以下的方法
// 如果测试数据量变大了就修改这个值
public static int MAXN = 101;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;
public static boolean isCompleteTree(TreeNode h) {
if (h == null) {
return true;
}
l = r = 0;
queue[r++] = h;
// 是否遇到过左右两个孩子不双全的节点
boolean leaf = false;
while (l < r) {
h = queue[l++];
if ((h.left == null && h.right != null) || (leaf && (h.left != null || h.right != null))) {
return false;
}
if (h.left != null) {
queue[r++] = h.left;
}
if (h.right != null) {
queue[r++] = h.right;
}
if (h.left == null || h.right == null) {
leaf = true;
}
}
return true;
}
}
求完全二叉树结点的个数，要求时间复杂度低于O（n）
算法思路
首先，对于一棵完全二叉树，我们一直往左遍历，可以求出树高
完全二叉树
右子树左边界达到总高
右子树左边界没有达到总高
代码实现
// 求完全二叉树的节点个数
public class Code09_CountCompleteTreeNodes {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 提交如下的方法
public static int countNodes(TreeNode head) {
if (head == null) {
return 0;
}
return f(head, 1, mostLeft(head, 1));
}
// cur : 当前来到的节点
// level : 当前来到的节点在第几层
// h : 整棵树的高度，不是cur这棵子树的高度
// 求 : cur这棵子树上有多少节点
public static int f(TreeNode cur, int level, int h) {
if (level == h) {
return 1;
}
if (mostLeft(cur.right, level + 1) == h) {
// cur右树上的最左节点，扎到了最深层
// 则可以计算出cur及其左树所含的结点总数
// 再对右树进行递归
return (1 << (h - level)) + f(cur.right, level + 1, h);
} else {
// cur右树上的最左节点，没扎到最深层
// 则可以计算出cur及其右树所含的结点总数
// 再对左树进行递归
return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
}
}
// 当前节点是cur，并且它在level层
// 返回从cur开始不停往左，能扎到几层
public static int mostLeft(TreeNode cur, int level) {
while (cur != null) {
level++;
cur = cur.left;
}
return level - 1;
}
}
时间复杂度分析
对于每个节点，最多向下树高h次，因此时间复杂度约为O（h2），远小于O（n）。
