LeetCode 补充题 194. 带层数的二叉树中序遍历
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 94. 二叉树的中序遍历
:::
给定二叉树
root，按照左子树、根、右子树的中序顺序返回[节点值, 层数]，根节点层数为1。
示例 1：
输入：
root = [2,1,3]
输出：[[1,2],[2,1],[3,2]]
提示：
- 允许空树。
- 节点值为
32位整数。
题意分析
输出顺序由中序遍历决定，层数由节点到根的路径决定，两者彼此独立。不能用输出位置推算层数，应当在递归下降时同时传递当前深度。
解法：携带深度的递归遍历
核心思路
[!blue]
定义递归过程接收节点和它的层数。空节点没有输出；非空节点先以层数加一访问左子树，再保存当前节点的值及层数，最后以层数加一访问右子树。
左子树的全部结果先于根、右子树的全部结果晚于根，因而满足中序顺序。根从层数 1 开始，每跨过一条父子边加一，记录的层数也正好对应实际位置。深度作为参数传递，返回后不会影响兄弟子树。
解题步骤
- 创建结果列表，从根节点及层数 1 开始递归。
- 空节点直接返回，否则递归访问左孩子，传入当前层数加一。
- 将当前节点值和当前层数组成一项加入结果。
- 以当前层数加一访问右孩子，完成后返回结果列表。
代码实现
class Solution {
public List<List<Integer>> inorderWithDepth(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
visit(root, 1, result);
return result;
}
private void visit(TreeNode node, int depth, List<List<Integer>> result) {
if (node == null) {
return;
}
visit(node.left, depth + 1, result);
result.add(Arrays.asList(node.val, depth));
visit(node.right, depth + 1, result);
}
}
func inorderWithDepth(root *TreeNode) [][]int {
result := [][]int{}
var visit func(*TreeNode, int)
visit = func(node *TreeNode, depth int) {
if node == nil {
return
}
visit(node.Left, depth+1)
result = append(result, []int{
node.Val,
depth,
})
visit(node.Right, depth+1)
}
visit(root, 1)
return result
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：辅助空间 $O(h)$，输出空间 $O(n)$。
关键点总结
[!green]
递归携带当前深度，在访问左右孩子时加一；在中序访问根的位置保存节点值与深度。
易错点总结
[!yellow]
- 根的层数从 1 开始，不是 0。
- 记录当前节点必须位于左、右子树递归之间。
- 空树返回空列表，不应输出空节点占位。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 94. 二叉树的中序遍历 | 简单 | 中序访问顺序相同；该题只返回节点值，本题还需随递归或栈记录深度，输出节点值与层数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！