/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function (root) {
const paths = [];
function findAllPaths(node, path) {
if (!node) return;
const { val, left, right } = node;
path.push(val);
!left && !right && paths.push(path.join("->"));
findAllPaths(node.left, path);
findAllPaths(node.right, path);
path.pop();
}
findAllPaths(root, []);
return paths;
};
时间复杂度和空间复杂度是多少？
时间空间复杂度都是O(2^N)
【以下回答由 GPT 生成】
这段代码的时间复杂度和空间复杂度如下：
时间复杂度： O(N) - N 是二叉树中节点的数量。算法的时间复杂度是线性的，因为它需要遍历所有的节点。
空间复杂度： O(N) - N 是二叉树中节点的数量。算法的空间复杂度主要取决于递归调用的深度，而递归调用的深度最多为树的高度。 - 在最坏的情况下，如果二叉树是一个链表（完全不平衡），那么递归调用的深度将是树的高度，即N。所以空间复杂度是O(N)。 - 在最好的情况下，如果二叉树是一个完美平衡树，那么递归调用的深度将是logN。所以空间复杂度是O(logN)。 - 每次递归调用时，都会创建一个新的path数组，用于存储当前路径上的节点值，这会消耗一些额外的空间。但是由于递归调用是在同一级别的栈帧中进行的，所以这不会导致空间复杂度增加。
综上所述，该算法的时间复杂度是O(N)，空间复杂度是O(N)或O(logN)。
【相关推荐】