[python][leetcode 129]. Sum Root to Leaf Numbers -- dfs,recur

 You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

 

  한줄해석. 

좌측과 같은 tree가 있을때, leaf노드 까지가서

그 합을 return 하면 된다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  알아야 할 개념: 

1.  tree 순회 방법  -> dfs로 구현(재귀),
   tree노드의 맨 끝까지 가야하니까 재귀의 탈출 조건은 node.left, node.right 가 둘다 None이여야한다. 
2. 부모노드에서 자식노드로 갈때, 값을 전달 해야한다. 현재 값을 전달 해야한다. 
3. 재귀에서 global을 통해서 값을 누적 시킬수 있다. (혹은 return 값 계속 더해도 될듯) 

    def sumNumbers(self, root: Optional[TreeNode]) -> int:

        global ret
        ret = 0
        def recur(node, x):   ## recur의 인자값은 tree노드를 순회하기위한 recur과
                              ## 값 누적을 위한 x 값을 인자로 가진다. 
            global ret
            if node.left is None and node.right is None: ## 맨끝일 경우 반환 .
                ret += 10 * x + node.val
            if node.left:
                recur(node.left, x*10+node.val)
            if node.right:
                recur(node.right, x*10+node.val)
            
    
        recur(root, 0)

        return ret

 

## global 안쓰면 아래처럼 가능
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def recur(node, x):
            temp = 0

            if node.right is None and node.left is None:
                temp += x * 10 + node.val
            
            if node.right:
                temp += recur(node.right,  x * 10 + node.val)
            
            if node.left:
                temp += recur(node.left, x * 10 + node.val)

            return temp

        return recur(root, 0)