[리트코드]3-4회차

 

https://leetcode.com/problems/sum-root-to-leaf-numbers/?envType=study-plan-v2&envId=top-interview-150

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def Numbers(self, root, curNum, sumNum):
        if not root:
            return int(curNum)
        
        curNum += str(root.val)

        if not root.left and not root.right: # 둘 다 없음
            sumNum += int(curNum)
        elif root.left and root.right:
            sumNum += self.Numbers(root.left, curNum, sumNum) + self.Numbers(root.right, curNum, sumNum)
        elif root.left: # left 만 존재
            sumNum += self.Numbers(root.left, curNum, sumNum) 
        elif root.right: # right 만 존재
            sumNum += self.Numbers(root.right, curNum, sumNum)

        return sumNum 

    def sumNumbers(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        sumNum = self.Numbers(root, "0", 0) 

        return sumNum

처음으로 풀었던 코드인데 조금 잡다한 줄이 많다.

 

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        def dfs(node, path_sum):
            if not node:
                return 0

            path_sum = path_sum * 10 + node.val
            if not node.left and not node.right:
                return path_sum
            
            return dfs(node.left, path_sum) + dfs(node.right, path_sum)

        return dfs(root, 0)

가장 많은 투표를 받았던 코드인데, 확실히 뭔가 깔끔하다. 저 조건문을 조금 다듬었다면 비슷하게 할 수 있었을까..? 일단 숫자를 int 로 바로 계산할 수 있게 한게 제일 깔끔하게 보이는 것 같다.

 

https://leetcode.com/problems/binary-tree-maximum-path-sum/?envType=study-plan-v2&envId=top-interview-150

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    maxNum = -1001

    def dfs(self, root):
            if not root:
                return -1001

            
            leftValue = self.dfs(root.left)
            rightValue = self.dfs(root.right)

            self.maxNum = max(leftValue, rightValue, self.maxNum, leftValue + rightValue + root.val, root.val)
        
            return leftValue + rightValue +root.val

    def maxPathSum(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        
        self.dfs(root)

        return self.maxNum

여기까지 진행했는데.. 저 음수를 처리하는 방법에서 막혀버렸다... 그래서 답안을 통해서 보완해본다!

 

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        max_path = float("-inf")
        def get_max_gain(node):
            nonlocal max_path
            if node is None:
                return 0

            gain_on_left = max(get_max_gain(node.left), 0)
            gain_on_right = max(get_max_gain(node.right), 0)

            current_max_path = node.val + gain_on_left + gain_on_right
            max_path = max(max_path,current_max_path)

            return node.val + max(gain_on_left, gain_on_right)

        get_max_gain(root)
        return max_path

 

이게 답안인데, 일단 만약 음수인경우 루트를 포함하지 않을 수 있도록 0으로 처리했다는 점이 가장 다른 것 같다. 이 코드를 바탕으로 원래 내 코드를 수정해본다.

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    maxNum = -1001

    def dfs(self, root):
            if not root:
                return 0

            
            leftValue = max(self.dfs(root.left), 0)
            rightValue = max(self.dfs(root.right), 0)

            self.maxNum = max(self.maxNum, leftValue + rightValue + root.val)
        
            return root.val + max(leftValue, rightValue)

    def maxPathSum(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        
        self.dfs(root)

        return self.maxNum

음.. 저 마지막에 왜 한쪽만 더하는 것인지 , 내가 질문을 잘 못 이해한 것인지 궁금해졌다.

 

내가 이해한게 맞다면, left + root + right 의 경우에는 root 가 최고 꼭대기에 있을 경우 가능하다. 그런데 리턴값의 경우에는 내가 최고 꼭대기에 있는게 아니므로 두개를 더한 값을 리턴하면 중복되어 길을 이용해야하는 문제가 발생해서 이렇다고 한다.