連結

129. Sum Root to Leaf Numbers
https://leetcode.com/problems/sum-root-to-leaf-numbers/

想法

1.一開始想到用 list 的方式去存放全部的路徑
2.最後在把全部路徑相加就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        branches = []
        self.my_sum(root, branches, root.val)
        return branches

    def my_sum(self, root, branch, total):
        if root.right:
            ...... # 加入路徑
        if root.left:
            ...... # 加入路徑
        if root.right.right:
            ...... # 加入路徑
        if root.left.right:
            ...... # 加入路徑
        if root.right.left:
            ...... # 加入路徑
        if root.left.left:
            ...... # 加入路徑
        .............. # 無限循環加入路徑
        return branch

之後依據這想法進行了改良

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        branches = []
        self.my_sum(root, branches, root.val)
        return branches

    def my_sum(self, root, branch, total):
        if root.right:
            branch.append(total*10+root.right.val)
            self.my_sum(root.right, branch, total*10+root.right.val)
        if root.left:
            branch.append(total*10+root.left.val)
            self.my_sum(root.left, branch, total*10+root.left.val)
        return branch
  • 出現有舊資料重複留存的現象
    Input：[4,9,0,5,1]
    Output：[40, 49, 491, 495]
    Expected：1026
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        branches = []
        # 只有一個則直接回傳
        if not root.left and not root.right:
            return root.val
        self.my_sum(root, branches, root.val)
        return sum(branches)

    def my_sum(self, root, branch, total):
        if root.right:
            # 刪掉重複的舊資料
            if total in branch:
                branch.remove(total)
            branch.append(total*10+root.right.val)
            self.my_sum(root.right, branch, total*10+root.right.val)
        if root.left:
            # 刪掉重複的舊資料
            if total in branch:
                branch.remove(total)
            branch.append(total*10+root.left.val)
            self.my_sum(root.left, branch, total*10+root.left.val)
        return branch
  • 使用if total in branch: branch.remove(total)的方式會有誤刪的問題，在 53145 分支時砍掉了 5314
    Input：
    Output：58981218
    Expected：58986532
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
                    5
             /             \
           3                 8
        /     \            /   
      0        1          3    
     / \      /  \       / \
    1   8    4    4     2   3
            / \        /     \
           5   4      7       6
                \      \       
                 1      6
                       /
                      8
                       \
                        7

改用branch.pop()來剔除重複元素，並改變原先的輸入方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 改成使用[root.val]傳入給函式，也刪除掉原本的特殊輸入直接回傳的部分
        branches = [root.val]
        self.my_sum(root, branches, root.val)
        return sum(branches)

    def my_sum(self, root, branch, total):
        # 改用branch.pop()來剔除重複元素
        if root.right or root.left:
            branch.pop()
        if root.right:
            branch.append(total*10+root.right.val)
            self.my_sum(root.right, branch, total*10+root.right.val)
        if root.left:
            branch.append(total*10+root.left.val)
            self.my_sum(root.left, branch, total*10+root.left.val)
        return branch