1022. 从根到叶的二进制数之和

🟢   🔖  树 深度优先搜索 二叉树  🔗 力扣 LeetCode

题目

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

• For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

Example 1:


Input: root = [1,0,1,0,1,0,1]

Output: 22

Explanation:(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2:

Input: root = [0]

Output: 0

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val is 0 or 1.

题目大意

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

• 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

示例 1：


输入： root = [1,0,1,0,1,0,1]

输出： 22

解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2：

输入： root = [0]

输出： 0

提示：

• 树中的节点数在 [1, 1000] 范围内
• Node.val 仅为 0 或 1

解题思路

我们可以通过 深度优先搜索（DFS） 来实现这一目标。

1. 深度优先搜索（DFS）：

   • 从根节点开始遍历，每次向下递归时，将父节点的值左移一位（相当于将二进制数向左移动一位）后加上当前节点的值，生成新的路径值。
   • 如果当前节点是叶子节点（没有左子节点和右子节点），则将当前路径值累加到结果中。

2. 递归传递路径值：

   • 每次递归时，将当前路径值作为参数传递到下一层，表示从根节点到当前节点的路径值。
   • 当遍历到叶子节点时，直接将该路径值加到结果变量中。

3. 返回结果：

   • 遍历完整棵树后，返回累加的路径值总和。

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点总数，每个节点都被访问一次。
• 空间复杂度：O(h)，其中 h 是树的高度，递归调用栈的深度为树的高度，
  • 最坏情况下（树为链状），h = n；
  • 最好情况下（树为完全平衡树），h = log(n)。

代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumRootToLeaf = function (root) {
	let sum = 0; // 用于存储路径值的总和

	// 定义递归函数
	const dfs = (root, parent) => {
		if (!root) return; // 如果节点为空，直接返回

		// 更新当前路径值
		const cur = (parent << 1) | root.val;

		// 如果当前节点是叶子节点
		if (!root.left && !root.right) {
			sum += cur; // 将路径值累加到总和中
		} else {
			// 递归遍历左子树和右子树
			dfs(root.left, cur);
			dfs(root.right, cur);
		}
	};

	// 从根节点开始 DFS，初始路径值为 0
	dfs(root, 0);

	return sum; // 返回路径值的总和
};