难度: Easy
给出一棵二叉树，其上每个结点的值都是 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 运行时间: 23 ms
内存: 0.0 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
result = 0
stack = [[root, root.val]]
while stack:
curr = stack.pop()
currTree = curr[0]
currVal = curr[1]
if currTree.left is None and currTree.right is None:
result += currVal
else:
if currTree.left:
stack.append([currTree.left, currVal * 2 + currTree.left.val])
if currTree.right:
stack.append([currTree.right, currVal * 2 + currTree.right.val])
return result
该题解采用了迭代的深度优先搜索（DFS）方法来解决问题。首先，如果根节点为空，则直接返回0。对于非空的树，使用一个栈来存储需要遍历的节点及其对应的当前二进制数值。栈的初始化包含根节点和其值。在遍历过程中，每次从栈中弹出一个元素，检查是否为叶子节点（即左右子树都为空）。如果是叶子节点，则将当前的二进制数值加到结果中。如果不是叶子节点，则对其非空的子节点进行处理，将子节点以及对应的更新后的二进制数值（当前值左移一位加上子节点的值，即currVal * 2 + currTree.child.val）压入栈中。这个过程重复直到栈为空，最后返回累加的结果。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
result = 0
stack = [[root, root.val]]
while stack:
curr, currVal = stack.pop()
if curr.left is None and curr.right is None:
result += currVal # Add the value of the leaf node
else:
if curr.left:
stack.append([curr.left, currVal * 2 + curr.left.val]) # Push left child with updated value
if curr.right:
stack.append([curr.right, currVal * 2 + curr.right.val]) # Push right child with updated value
return result
迭代的DFS使用显式的栈来控制遍历过程，这样可以避免递归造成的栈溢出问题，特别是在处理非常深的树时更加安全。此外，迭代方法可以让内存使用更加可控，易于调试和理解，尤其是在复杂的二进制数处理中。
确实有可能出现整数溢出的情况。Python 的整数类型在内部会自动转为长整型来处理大数，因此在Python中不会产生传统意义上的溢出错误，但在其他一些语言中，如Java或C++，可能需要特别处理，比如使用长整形数据类型或者在每次累加后进行模运算以避免溢出。
在迭代过程中，每个栈元素都包含当前节点以及从根到该节点的累积二进制数值。每当访问一个节点时，我们根据其父节点的二进制数值计算当前节点的二进制数值（左移并加上当前节点值）。这种方法确保了每次从栈中弹出的元素都能准确地反映从根节点到当前节点的完整路径值。
如果一个节点的左或右子节点为null，这意味着这个方向没有子树，因此在处理时只需将非null的子节点和对应的二进制数值推入到栈中。具体来说，如果左子节点为null，只处理右子节点；如果右子节点为null，只处理左子节点。这样保证了只有存在的路径被考虑进最终的累加结果。