257. 二叉树的所有路径

🟢   🔖  树 深度优先搜索 字符串 回溯 二叉树  🔗 力扣 LeetCode

题目

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]

Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]

Output: ["1"]

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• -100 <= Node.val <= 100

题目大意

给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。

解题思路

Google 的面试题，考察递归。

1. 从根节点开始，递归遍历左子树和右子树。
2. 将当前节点的值与左子树或右子树返回的路径拼接，构建完整的路径。
3. 当遍历到叶子节点时，将该路径存入结果中。
4. 将左子树和右子树的路径合并，形成完整的从根节点到各个叶子节点的路径并返回。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是二叉树的节点数。由于需要访问所有 n 个节点，并且每次递归调用都进行字符串拼接操作，拼接的操作是与路径长度成比例的，在最坏情况下，树是链状的，路径的长度为 O(n)。因此，总体的时间复杂度为 O(n^2)。

• 空间复杂度：O(log n)，递归调用栈的最大深度由树的高度决定，在最好的情况下，树是完全平衡的，递归深度为 O(log n)；在最坏情况下，树是链状的，递归深度为 O(n)。

代码

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
	let res = [];
	if (!root) return res;
	if (!root.left && !root.right) return ['' + root.val];
	let tempLeft = binaryTreePaths(root.left);
	for (let i of tempLeft) {
		res.push(root.val + '->' + i);
	}
	let tempRight = binaryTreePaths(root.right);
	for (let i of tempRight) {
		res.push(root.val + '->' + i);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
113	路径总和 II	[✓]	树 深度优先搜索 回溯 1+
988	从叶结点开始的最小字符串		树 深度优先搜索 字符串 2+
2096	从二叉树一个节点到另一个节点每一步的方向		树 深度优先搜索 字符串 1+