目录
宽搜（BFS）
N 叉树的层序遍历
二叉树的锯齿形层序遍历
二叉树最大宽度
在每个树行中找最大值
宽搜（BFS）
N 叉树的层序遍历
429. N 叉树的层序遍历 - 力扣（LeetCode）
/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ret = new ArrayList<>();if (root == null)return ret;Queue<Node> q = new LinkedList<>();// 使用队列q.add(root);while (!q.isEmpty()) {int sz = q.size();List<Integer> tmp = new ArrayList<>();// 统计本层的节点信息for (int i = 0; i < sz; i++) {Node t = q.poll();tmp.add(t.val);for (Node child : t.children) {if (child != null) {q.add(child);// 孩子入队}}}ret.add(tmp);}return ret;}
}二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
解法：层序遍历
增加一个标记位，让偶数行的信息逆序即可 Collections.reverse();
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();// 用来返回结果if (root == null)return ret;// 判空Queue<TreeNode> q = new LinkedList<>();q.add(root);// 用来获取二叉树中元素int level = 1;// 标记是否是偶数行while (!q.isEmpty()) {int sz = q.size();List<Integer> tmp = new LinkedList<>();// 用来记录每一行结果for (int i = 0; i < sz; i++) {TreeNode t = q.poll();tmp.add(t.val);if (t.left != null)q.add(t.left);if (t.right != null)q.add(t.right);}// 判断是否逆序if (level % 2 == 0)Collections.reverse(tmp);ret.add(tmp);level++;}return ret;}
}二叉树最大宽度
662. 二叉树最大宽度 - 力扣（LeetCode）
解法一：硬补 -> 超时、内存可能不够
解法二：利用数组存储二叉树的方式（堆），给节点编号
细节：①用数组来实现队列，这样队头队尾比较好找
②下标可能溢出。相减之后，即使溢出，结果也是正确的（数据存储是环形的，距离不会溢出）
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int widthOfBinaryTree(TreeNode root) {List<Pair<TreeNode, Integer>> q = new ArrayList<>();// 用数组模拟队列q.add(new Pair<TreeNode, Integer>(root, 1));int ret = 0;// 记录最终结果while (!q.isEmpty()) {Pair<TreeNode, Integer> t1 = q.get(0);// 得到队头Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);// 得到队尾ret = Math.max(t2.getValue() - t1.getValue() + 1, ret);// 下一层进队List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();for (Pair<TreeNode, Integer> t : q) {TreeNode node = t.getKey();int index = t.getValue();if (node.left != null) {tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));}if (node.right != null) {tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));}}q = tmp;}return ret;}
}在每个树行中找最大值
515. 在每个树行中找最大值 - 力扣（LeetCode）
解法：利用层序遍历，统计出每一层最大值
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ret = new ArrayList<>();if (root == null)return ret;Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {int sz = q.size();int tmp = Integer.MIN_VALUE;for (int i = 0; i < sz; i++) {TreeNode t = q.poll();tmp = Math.max(tmp, t.val);if (t.left != null)q.add(t.left);if (t.right != null)q.add(t.right);}ret.add(tmp);}return ret;}
}