Trees - Top Interview Questions[EASY] (4/9) : Python

leetcode.com/problems/maximum-depth-of-binary-tree/

class Solution:        
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        stack = []
        if root is not None:
            stack.append((1, root))
        depth = 0
        while stack != []:
            current_depth, root = stack.pop()
            if root is not None:
                depth = max(depth, current_depth)
                stack.append((current_depth+1, root.left))
                stack.append((current_depth+1, root.right))
        return depth

leetcode.com/problems/validate-binary-search-tree/

내코드

class Solution:
    def dfs(self, node:TreeNode, low:TreeNode, high:TreeNode) -> bool:
        if node is None: return True
        
        if low is not None and node.val <= low.val:
            return False
        if high is not None and node.val >= high.val:
            return False
            
        return self.dfs(node.left, low, node) and self.dfs(node.right, node, high)
        
    def isValidBST(self, root: TreeNode) -> bool:
        return self.dfs(root, None, None)

솔루션코드

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        
        def validate(node, low=-math.inf, high=math.inf):
            # Empty trees are valid BSTs.
            if not node:
                return True
            # The current node's value must be between low and high.
            if node.val <= low or node.val >= high:
                return False
            
            # The left and right subtree must also be valid.
            return (validate(node.right, node.val, high) and
                   validate(node.left, low, node.val))
        
        return validate(root)

이터레이션

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        stack = [(root, -math.inf, math.inf)]
        while stack:
            root, lower, upper = stack.pop()
            if not root:
                continue
            val = root.val
            if val <= lower or val >= upper:
                return False
            stack.append((root.right, val, upper))
            stack.append((root.left, lower, val))
        return True

그리고 이거 풀이가 여러가지 버전이 있는데 볼 시간이 없네.

leetcode.com/problems/symmetric-tree/

대칭 구성하는 부분이 아직 익숙치 않은 느낌.

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        
        def check(left: TreeNode, right: TreeNode): 
            if left is None and right is None:
                return True
            if left is None or right is None:
                return False
            return left.val == right.val and check(left.right, right.left) and check(left.left, right.right)
        
        return check(root, root)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        que = []
        que.append(root)
        que.append(root)
        while que:
            left = que.pop()
            right = que.pop()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            que.append(left.left);
            que.append(right.right);
            que.append(left.right);
            que.append(right.left);
        return True

leetcode.com/problems/binary-tree-level-order-traversal/

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if not root:
            return levels
        
        def helper(node, level):
            if len(levels) == level:
                levels.append([])
            levels[level].append(node.val)
            if node.left:
                helper(node.left, level+1)
            if node.right:
                helper(node.right, level+1)
        helper(root, 0)
        return levels

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if not root:
            return levels
        
        level = 0
        queue = deque([root,])
        while queue:
            levels.append([])
            level_length = len(queue)
            
            for i in range(level_length):
                node = queue.popleft()
                levels[level].append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            level += 1
        return levels

leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            
            p = (left + right) // 2
            
            root = TreeNode(nums[p])
            root.left = helper(left, p-1)
            root.right = helper(p+1, right)
            return root
        
        return helper(0, len(nums)-1)

리트코드 코딩 인터뷰 문제 목록(EASY) - Java

Array - Top Interview Questions[EASY] (1/9) : Java

String - Top Interview Questions[EASY] (2/9) : Java

Linked List - Top Interview Questions[EASY] (3/9) : Java

Trees - Top Interview Questions[EASY] (4/9) : Java

Sorting and Searching - Top Interview Questions[EASY] (5/9) : Java

Dynamic Programming - Top Interview Questions[EASY] (6/9) : Java

Design - Top Interview Questions[EASY] (7/9) - Java

Math - Top Interview Questions[EASY] (8/9) - Java

Others - Top Interview Questions(EASY) - (9/9) : Java

리트코드 코딩 인터뷰 문제 목록(EASY) - Python

Array - Top Interview Questions[EASY] (1/9) : Python