深度优先遍历 DFS
解题思路
在深度优先搜索遍历二叉树时，需要考虑当前的节点以及它的孩子节点：
- 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点；
- 如果当前节点是叶子节点，则在当前路径末尾添加该节点后就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可；
如此，当遍历完整棵二叉树以后就得到了所有从根节点到叶子节点的路径；
复杂度
-
时间复杂度：
O(N)，其中 N 表示节点数目； -
空间复杂度：
O(N^2)，其中 N 表示节点数目;- 在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N ，此时每一层的 path 变量的空间代价的总和为
O(N^2）; - 最好情况下，当二叉树为平衡二叉树时，它的高度为 logN ，此时空间复杂度为
O((logN)^2);
- 在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N ，此时每一层的 path 变量的空间代价的总和为
代码实现
var binaryTreePaths = function (root) {
let res = [];
travese(root, res, []);
return res;
};
const travese = (node, res, path = []) => {
if (node === null) return null;
// 叶子节点
if (node.left === null && node.right === null) {
path.push(node.val);
res.push(path.join('->'));
}
travese(node.left, res, path.concat(node.val));
travese(node.right, res, path.concat(node.val));
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 876. 链表的中间节点
上一篇
评论
