[LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和
2023-09-27 14:28:37 时间
Given a binary tree containing digits from 0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path1->2
represents the number12
. The root-to-leaf path1->3
represents the number13
. Therefore, sum = 12 + 13 =25
.
Example 2:
Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: The root-to-leaf path4->9->5
represents the number 495. The root-to-leaf path4->9->1
represents the number 491. The root-to-leaf path4->0
represents the number 40. Therefore, sum = 495 + 491 + 40 =1026
.
给一个只含有数字0-9的二叉树,每一个从根节点到叶节点的路径代表一个数字,求所有这些数字的和。
解法1:递归,累加所有路径上节点的值,每多一层之前的值要扩大十倍。
解法2: 迭代,while循环,用stack或queue来存下一层的节点和之前的和。TLE
Java:
public int sumNumbers(TreeNode root) { return sum(root, 0); } public int sum(TreeNode n, int s){ if (n == null) return 0; if (n.right == null && n.left == null) return s*10 + n.val; return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val); }
Python:
# Time: O(n) # Space: O(h), h is height of binary tree class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): # @param root, a tree node # @return an integer def sumNumbers(self, root): return self.sumNumbersRecu(root, 0) def sumNumbersRecu(self, root, num): if root is None: return 0 if root.left is None and root.right is None: return num * 10 + root.val return self.sumNumbersRecu(root.left, num * 10 + root.val) + self.sumNumbersRecu(root.right, num * 10 + root.val)
Python: bfs + stack
def sumNumbers1(self, root): if not root: return 0 stack, res = [(root, root.val)], 0 while stack: node, value = stack.pop() if node: if not node.left and not node.right: res += value if node.right: stack.append((node.right, value*10+node.right.val)) if node.left: stack.append((node.left, value*10+node.left.val)) return res
Python: bfs + queue
# def sumNumbers2(self, root): if not root: return 0 queue, res = collections.deque([(root, root.val)]), 0 while queue: node, value = queue.popleft() if node: if not node.left and not node.right: res += value if node.left: queue.append((node.left, value*10+node.left.val)) if node.right: queue.append((node.right, value*10+node.right.val)) return res
Python: Recursive
def sumNumbers(self, root): self.res = 0 self.dfs(root, 0) return self.res def dfs(self, root, value): if root: #if not root.left and not root.right: # self.res += value*10 + root.val self.dfs(root.left, value*10+root.val) #if not root.left and not root.right: # self.res += value*10 + root.val self.dfs(root.right, value*10+root.val) if not root.left and not root.right: self.res += value*10 + root.val
C++:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int sumNumbers(TreeNode *root) { return sumNumbersDFS(root, 0); } int sumNumbersDFS(TreeNode *root, int sum) { if (!root) return 0; sum = sum * 10 + root->val; if (!root->left && !root->right) return sum; return sumNumbersDFS(root->left, sum) + sumNumbersDFS(root->right, sum); } };
类似题目:
[LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和
All LeetCode Questions List 题目汇总
相关文章
- Leetcode: Power of Four
- Leetcode: Coin Change
- Leetcode: Search in Rotated Sorted Array II
- 【Leetcode】104. 二叉树的最大深度(简单)
- 【Leetcode】剑指 Offer 18. 删除链表的节点(简单)
- LeetCode左程云算法课笔记(整理ing)
- JS Leetcode 26. 删除有序数组中的重复项 题解分析,字典与快慢双指针
- 【看懂LeetCode】2.两数相加
- [LeetCode]剑指 Offer 22. 链表中倒数第k个节点
- LeetCode之024两两交换链表中的节点(相关话题:链表递归迭代)
- 93、【树与二叉树】leetcode ——222. 完全二叉树的节点个数:普通二叉树求法+完全二叉树性质求法(C++版本)
- 【LeetCode】27. Remove Element (2 solutions)
- [LeetCode] 1249. Minimum Remove to Make Valid Parentheses 移除无效的括号
- [LeetCode] 1090. Largest Values From Labels 标签中的最大价值
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- [LeetCode] 924. Minimize Malware Spread 最大程度上减少恶意软件的传播
- [LeetCode] 24 Game 二十四点游戏
- [LeetCode] Valid Word Square 验证单词平方
- [LeetCode] 285. Inorder Successor in BST 二叉搜索树中的中序后继节点
- [LeetCode] 234. Palindrome Linked List 回文链表