이진트리 추가문제

Question 1: Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

입력: root = [5,1,4,null,null,3,6]

출력: false

내 풀이

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(node:TreeNode):
            if not node:
                return             

            if node.left and node.left.val >= node.val: 
                return False
            
            if node.right and node.right.val <= node.val:
                return False
            
            dfs(node.left)
            dfs(node.right)
            return True
        
        return dfs(root)

• 오른쪽의 서브트리는 노드의 값보다 전부 커야하고 왼쪽의 서브트리는 노드의 값보다 전부 작아야 하는 것을 고려하지 않았다.
• 결국 에러가 떴다.

다른 풀이 방법

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def checkRange(node: TreeNode, lo: int, hi:int) -> bool:
            if not node:
                return True
            elif lo is not None and node.val <= lo:
                return False
            elif hi is not None and node.val >= hi:
                return False
            return checkRange(node.left, lo, node.val) and checkRange(node.right, node.val, hi)

        return checkRange(root, None, None)

• 노드가 가질 수 있는 최솟값과 최댓값을 인수로 넣어 재귀 호출하였다.
• node.left 를 재귀 호출 할 때는 노드의 값을 최댓값 인수에 넣었고
• node.right 를 재귀 호출 할 때는 노드의 값을 최솟값 인수로 넣었다.

Question 2: Path Sum 2

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

입력: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

출력: [[5,4,11,2],[5,8,4,5]]

내 풀이

class Solution:
    
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        answer = []
        lst = []
        def dfs(node:TreeNode, target:int):
            if node:
                lst.append(node.val)            
                if target == node.val and not (node.left or node.right):
                    answer.append(lst[:])
                dfs(node.left, target-node.val)
                dfs(node.right, target-node.val)
                lst.pop()
                
        dfs(root, targetSum)
        return answer

• 처음에는 root to leaf 라는 조건을 보지 못하여서 if문에 해당 조건을 설정하지 않아서 계속 에러가 났다.
• and not (node.left or node.right) 을 추가하였더니 더 이상의 에러가 나지 않았다.

결과

Runtime: 60 ms, faster than 59.52% of Python3 online submissions for Path Sum II. Memory Usage: 15.7 MB, less than 58.75% of Python3 online submissions for Path Sum II.