129. Sum Root to Leaf Numbers (Tree, Depth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/sum-root-to-leaf-numbers/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) DFS

이런 문제는 바로 DFS가 떠올라야 한다. Leaf node까지 가고 나서 ans에 답을 더하는 식이므로 leaf node를 만족하는지 체크하는 if문을 넣어야 할 것이다.

# 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:
        ans = 0

        def dfs(node, cur_sum):
            if not node:
                return

            cur_sum = cur_sum * 10 + node.val
            if not node.left and not node.right:
                nonlocal ans
                ans += cur_sum
                return
            else:
                dfs(node.left, cur_sum)
                dfs(node.right, cur_sum)

        dfs(root, 0)
        return ans

Time Complexity: O(n) n개의 노드들을 방문하기 때문이다.

Space Complexity: O(h) 여기서 h는 Tree의 Height이다.

2) Morris Preorder Traversal

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        root_to_leaf = curr_number = 0

        while root:
            # If there is a left child,
            # then compute the predecessor.
            # If there is no link predecessor.right = root --> set it.
            # If there is a link predecessor.right = root --> break it.
            if root.left:
                # Predecessor node is one step to the left
                # and then to the right till you can.
                predecessor = root.left
                steps = 1
                while predecessor.right and predecessor.right is not root:
                    predecessor = predecessor.right
                    steps += 1

                # Set link predecessor.right = root
                # and go to explore the left subtree
                if predecessor.right is None:
                    curr_number = curr_number * 10 + root.val
                    predecessor.right = root
                    root = root.left
                # Break the link predecessor.right = root
                # Once the link is broken,
                # it's time to change subtree and go to the right
                else:
                    # If you're on the leaf, update the sum
                    if predecessor.left is None:
                        root_to_leaf += curr_number
                    # This part of tree is explored, backtrack
                    for _ in range(steps):
                        curr_number //= 10
                    predecessor.right = None
                    root = root.right

            # If there is no left child
            # then just go right.
            else:
                curr_number = curr_number * 10 + root.val
                # if you're on the leaf, update the sum
                if root.right is None:
                    root_to_leaf += curr_number
                root = root.right

        return root_to_leaf

Time Complexity: O(n)

Space Complexity: O(1)