0257. Binary Tree Paths
=======================
题目信息
--------
:题号: 0257
:难度: Easy
:主题: 二叉树、根到叶路径、深度优先搜索、字符串
:原题: `LeetCode 0257 `_
:重点: 只收集根到叶节点的完整路径、使用 ``->`` 连接节点值、结果顺序不限
题目重述
--------
给定一棵非空二叉树的根节点 ``root``,返回树中所有从根节点到叶节点的路径。叶节点是左右子节点都为空的节点;路径必须在叶节点处结束,不能把通往内部节点的前缀当作答案。
每条路径以字符串表示,节点值按访问顺序排列,相邻节点之间使用 ``"->"`` 连接。树中节点数位于 ``[1, 100]``,节点值位于 ``[-100, 100]``。多个路径可以按任意顺序返回,函数不需要修改树的结构或节点值。
自建示例
--------
存在不同深度的叶节点:
.. code-block:: text
输入:root = [8, 3, 10, 1, 6, null, 14]
输出:["8->3->1", "8->3->6", "8->10->14"]
解释:节点 1、6 和 14 的左右子节点都为空,因此三条从根到它们的路径都是答案;输出顺序也可以不同。
只有一个节点:
.. code-block:: text
输入:root = [-4]
输出:["-4"]
解释:根节点本身也是叶节点,所以唯一的根到叶路径只包含它自身。
DFS 只在叶节点收集路径
----------------------
递归参数保存当前节点和从根到当前节点的字符串。进入节点时追加节点值;
若左右孩子都为空,当前字符串才是一条完整答案。若当前节点是内部节点,则分别递归非空孩子,
不能在这里提前收集,否则会把根到内部节点的前缀误当成根到叶路径。
为了避免每次递归复制整条字符串,使用回溯:记住进入前的长度,追加当前节点和连接符,
处理完左右子树后恢复到旧长度。负数通过 ``std::to_string`` 直接格式化,连接符只出现在相邻节点之间。
正确性说明
----------
递归进入一个节点时,路径字符串恰好是根到该节点的唯一路径。若它是叶节点,字符串满足答案定义;
若不是叶节点,所有合法根到叶路径都必须继续进入其左或右非空子树,递归会覆盖这两种选择。
回溯只恢复局部字符串,不改变已经加入结果的副本,因此每条叶路径恰好被收集一次。
C++ 实现
--------
.. code-block:: cpp
class Solution {
void collect(TreeNode* node, std::string& path,
std::vector& answer) {
const std::size_t old_size = path.size();
if (!path.empty()) path += "->";
path += std::to_string(node->val);
if (node->left == nullptr && node->right == nullptr) {
answer.push_back(path);
} else {
if (node->left != nullptr) collect(node->left, path, answer);
if (node->right != nullptr) collect(node->right, path, answer);
}
path.resize(old_size);
}
public:
std::vector binaryTreePaths(TreeNode* root) {
std::vector answer;
if (root == nullptr) return answer;
std::string path;
collect(root, path, answer);
return answer;
}
};
代码分析
--------
每个节点只访问一次;追加路径和复制叶路径的成本与输出字符串长度相关,遍历本身为 ``O(n)``,
总时间可写为 ``O(n + 输出总字符数)``。回溯字符串和递归栈占 ``O(h)``,结果数组的空间属于输出,
树结构和值均不修改。