本篇文章主要是二叉树关于「行」操作技巧的相关总结
自己也是写了两个类似的题目，首先是根据自己的惯性思维求解，但是最后对比其他人的解法后，发现了一些隐藏 (自己不知道的) 的技巧
众所周知，对行操作最基本的方法就是「层次遍历」，维护一个队列存储每一行的节点。基本上很多题目都可以利用层次遍历的变形求解
如：二叉树的右视图、二叉树的锯齿形层序遍历、二叉树的层序遍历 II 等等
但是本篇文章要介绍的是另外两个题目：在每个树行中找最大值 和 二叉树最大宽度。分别会使用「惯性思维 (层序遍历)」和「隐藏技巧 (递归遍历)」两种方法解决
这两个题目的共同点都是计算每一行的某些属性，如：每行中最大值、所有行中的最大宽度。根据惯性思维，很容易想到利用层次遍历求解
题目详情可见 在每个树行中找最大值
xxxxxxxxxx// 题目：在每个树行中找最大值public List<Integer> largestValues(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int n = q.size(); // 每次对一行进行循环时，维护一个 max 变量 int max = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { TreeNode cur = q.poll(); // 更新 max 的值 max = Math.max(max, cur.val); if (cur.left != null) q.offer(cur.left); if (cur.right != null) q.offer(cur.right); } res.add(max); } return res;}题目详情可见 二叉树最大宽度
x
// 建议点击上面的链接仔细看一下题目，两个非空节点的中间 null 节点也算长度// 引入一个概念：如果从根节点开始从 1 开始编号，那么如果父节点为 i，那么左孩子和右孩子分别为 2*i，2*i+1// 计算两个非空节点之间的长度，只需要根据节点编号相减即可class Solution { // 新数据结构：为每一个节点绑定一个编号 id class Pair { TreeNode node; int id; public Pair(TreeNode node, int id) { this.node = node; this.id = id; } } public int widthOfBinaryTree(TreeNode root) { if (root == null) return 0; Queue<Pair> q = new LinkedList<>(); q.offer(new Pair(root, 1)); int res = Integer.MIN_VALUE; while (!q.isEmpty()) { int n = q.size(); // 每行中第一个非空节点编号 int first = -1; // 每行中最后一个非空节点编号 int last = -1; for (int i = 0; i < n; i++) { Pair cur = q.poll(); if (cur.node.left != null) q.offer(new Pair(cur.node.left, cur.id * 2)); if (cur.node.right != null) q.offer(new Pair(cur.node.right, cur.id * 2 + 1)); // 如果 first == -1，说明 first 未更新，则记录遇到的第一个节点编号 first = first == -1 ? cur.id : first; // 一直更新 last 的编号，直到最后一个 last = cur.id; } // 当前行宽度：last - first + 1 // 更新最大值 res = Math.max(res, last - first + 1); } return res; }}下面介绍一种递归的解法，并且引入了「深度」的概念
介绍递归解法前，先介绍一下树的深度。相信大家对于如何求树的深度已经了如指掌，不确定的可以先去写一下 二叉树的最大深度 和 二叉树的最小深度
下面给出「带着深度信息」的遍历框架，这个是很有用的，因为很多处理行问题的时候都需要根据深度判断元素是否属于同一行
xxxxxxxxxxpublic void traversal(TreeNode root, int curDepth) { if (root == null) return ; // 先序遍历处理阶段 traversal(root.left, curDepth + 1); traversal(root.right, curDepth + 1); // 后序遍历处理阶段}// 调用：root 节点深度为 1traversal(root, 1);题目详情可见 在每个树行中找最大值
x
class Solution { private List<Integer> res = new ArrayList<>(); public List<Integer> largestValues(TreeNode root) { if (root == null) return res; traversal(root, 1); return res; } private void traversal(TreeNode root, int curDepth) { if (root == null) return ;
// ------- 核心代码 ------- // 先序遍历可以保证每一层的第一个非空节点都是按照深度的顺序加入 List 中的 // res.size() < curDepth 说明第一次到达该层，直接加入 List 中 if (res.size() < curDepth) { res.add(root.val); } else { // 说明非首次到达该层，比较 res.get(curDepth - 1) 和 root.val 的大小，取最大值，更新 List (curDepth - 1) 处值 // 这样可以保证最后每层在 List 中的元素都是最大值 res.set(curDepth - 1, Math.max(res.get(curDepth - 1), root.val)); } // --------- End ---------
traversal(root.left, curDepth + 1); traversal(root.right, curDepth + 1); }}题目详情可见 二叉树最大宽度
xxxxxxxxxxclass Solution { // 存放每一行的首个非空节点的编号 private List<Integer> firstId = new ArrayList<>(); private int maxWidth = 0; public int widthOfBinaryTree(TreeNode root) { if (root == null) return 0; traversal(root, 1, 1); return maxWidth; } // 第二个参数：节点编号 // 上述说明了父节点和孩子节点的关系 private void traversal(TreeNode root, int id, int curDepth) { if (root == null) return ; // 同上 if (firstId.size() < curDepth) { firstId.add(id); } maxWidth = Math.max(maxWidth, id - firstId.get(curDepth - 1) + 1);
traversal(root.left, 2 * id, curDepth + 1); traversal(root.right, 2 * id + 1, curDepth + 1); }}到此为止，完美收官！！！哈哈哈哈哈哈