leetcode ２分木

２分木の問題を解く時の頻出アルゴリズム

再帰関数の中で「右の木」と「左の木」に分けて、再帰関数に再代入する。

Passするプログラムの形（おそらく。。。）

def 再帰関数:
    if node is None:
        return
    毎回する処理
    再帰関数(右の木)
    再帰関数(左の木)

ポイントはreturnを各場所です！

Passしたコード

# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        nums = []
        tmp = ''
        def _make_number_from_Tree(node:TreeNode, tmp:str):
            if node is None:
                return 

            tmp += str(node.val)
            if node.right is None and node.left is None:
                nums.append(int(tmp))
            _make_number_from_Tree(node.right, tmp)
            _make_number_from_Tree(node.left, tmp)
        
        _make_number_from_Tree(root, tmp)
        return sum(nums)

失敗例１

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    nums = []
    tmp = ''
    def _make_number_from_Tree(node:TreeNode, tmp:str):
        tmp += str(node.val)
        if node.right is not None:
            _make_number_from_Tree(node.right, tmp)
        if node.left is not None:
            _make_number_from_Tree(node.left, tmp)
        nums.append(int(tmp))
        return 
        
    _make_number_from_Tree(root, tmp)
    return sum(nums)

失敗例２

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    nums = []
    tmp = ''
    def _make_number_from_Tree(node:TreeNode, tmp:str):
        tmp += str(node.val)
        if node.right is None:
            nums.append(int(tmp))
            return 
        else:
            _make_number_from_Tree(node.right, tmp)

        if node.left is None:
            nums.append(int(tmp))
            return
        else:
            _make_number_from_Tree(node.left, tmp)
    _make_number_from_Tree(root, tmp)
    return sum(nums)