题目:
求根到叶子节点数字之和:给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。 例如,从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。
思路:
深度优先。
程序:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sumNumbers(self, root: TreeNode) -> int: if not root: return 0 result = [] stack_sum = [] stack_node = [] stack_sum.append(str(root.val)) stack_node.append(root) while stack_sum and stack_node: auxiliary_sum = stack_sum.pop() auxiliary_node = stack_node.pop() if auxiliary_node.left: stack_sum.append(auxiliary_sum + str(auxiliary_node.left.val)) stack_node.append(auxiliary_node.left) if auxiliary_node.right: stack_sum.append(auxiliary_sum + str(auxiliary_node.right.val)) stack_node.append(auxiliary_node.right) if not auxiliary_node.left and not auxiliary_node.right: result.append(int(auxiliary_sum)) return sum(result)