叶子节点

首先我们需要明确这个问题的目标即找到所有从根节点到叶节点的路径。

对于每一条路径我们需要把其中的每个节点的值按顺序连接起来形成一个字符串并将其保存在一个字符串数组中返回。

通过观察代码我们可以发现该题解中使用了递归的思想来解决问题。

具体来说它定义了一个名为

traversal

node-leftNULLnode-rightNULL如果是则将

path

中我们首先判断根节点是否为空如果为空则返回空的字符串数组否则我们调用

traversal

O(n)。

特别地如果所有的节点都在同一条路径上递归栈的最大深度将是

n在这种情况下空间复杂度将达到

将当前节点的值添加到路径中path.push_back(node-val);//

如果当前节点是叶节点则将路径转化为字符串并添加到结果数组中if

(node-left

添加最后一个节点的值ans.push_back(sPath);

递归遍历左子树if

返回上一层递归之前弹出当前节点恢复路径状态}}vectorstring

root)

特殊情况处理空树直接返回空结果数组traversal(root,

path,

{ans.push_back(path);return;}//

添加箭头符号分隔路径节点path