# 1022. Sum of Root To Leaf Binary Numbers
###### tags: `leetcode` `tree` `easy` `1022` `2021-05-09`
## :memo: My first solution
```
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
```
* 上圖是用這個題目給的範例去思考
* :medal: **思考一**:一看到 Tree 的題目我會直覺得想用 dfs 遞迴的方式解掉
* :medal: **思考二**:如果我把所有的數字產生的結果都找出來然後轉成十進位再全部加上就可以得到答案了。
```python=
# 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: TreeNode) -> int:
anslist = []
self.helper(root, '', anslist)
answer = 0
for i in anslist:
answer += int(i,2)
return answer
def helper(self, root, temp, anslist):
if not root:
anslist.append(temp)
return
if not root.left and not root.right:
anslist.append(temp + str(root.val))
return
elif not root.left:
self.helper(root.right, temp + str(root.val), anslist)
elif not root.right:
self.helper(root.left, temp + str(root.val), anslist)
else:
self.helper(root.right, temp + str(root.val), anslist)
self.helper(root.left, temp + str(root.val), anslist)
```
:-1: **檢討**
1. code 22行到24行是不需要的，因為題目有跟你說過至少有一個 node。
2. 二進位轉十進位的 function，請記熟。
```python=
int('11',2) => 3
```
3. code 30到34行可以去掉
```python=
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
anslist = []
self.helper(root, '', anslist)
answer = 0
for i in anslist:
answer += int(i,2)
return answer
def helper(self, root, temp, anslist):
if not root:
return
if not root.left and not root.right:
anslist.append(temp + str(root.val))
return
self.helper(root.right, temp + str(root.val), anslist)
self.helper(root.left, temp + str(root.val), anslist)
```
:mag: **bigO**
時間複雜度: 2n(n 個 node)
空間複雜度: n(n 個 node)
## :memo: leetcode solution
> Prerequisites: Bitwise Trick
> If you work with decimal representation, the conversion of 1->2 into 12 is easy. You start from curr_number = 1, then shift one register to the left and add the next digit: curr_number = 1 * 10 + 2 = 12.
> If you work with binaries 1 -> 1 -> 3, it's the same. You start from curr_number = 1, then shift one register to the left and add the next digit: curr_number = (1 << 1) | 1 = 3.
[外部參考連結](http://web.ntnu.edu.tw/~algo/Bit.html)
```python=
ans = (1 << 1) | 1
# ans = 3
ans = (1 << 1) | 0
# ans = 2
(1 << 1) | 0
# ^^
# 數字1
# ^^
# 往左移一格
# ^^ OR with 0
(2 << 1) | 1
# 5
```
根據 leetcode 的 solution，然後修正完的寫法
:memo: 寫法一
```python=
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
self.answer = 0
self.helper(root, 0)
return self.answer
def helper(self, root, current_num):
if root:
current_num = current_num << 1 | root.val
if not root.left and not root.right:
self.answer += current_num
self.helper(root.right, current_num)
self.helper(root.left, current_num)
```
:memo: 寫法二 -> 我自己會用這種寫法，我的邏輯思考比較符合這樣
```python=
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
self.answer = 0
self.helper(root, 0)
return self.answer
def helper(self, root, current_num):
if not root:
return
current_num = current_num << 1 | root.val
if not root.left and not root.right:
self.answer += current_num
return
self.helper(root.right, current_num)
self.helper(root.left, current_num)
```
:mag: **bigO**
時間複雜度: n(n 個 node)
空間複雜度: H(tree 的高度)
Sign in with Wallet
Connect another wallet