23.07.10 Today’s Leetcode

111. Minimum Depth of Binary Tree (easy)

# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        res = 10**9
        if root.left:
            res = min(res, self.minDepth(root.left))
        if root.right:
            res = min(res, self.minDepth(root.right))
        if res != 10**9:
            return res + 1
        return res

1361. Validate Binary Tree Nodes (medium)

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

        used = set()
        def dfs(cur):
            nonlocal used
            if cur == -1:
                return True
            if cur in used:
                return False

            used.add(cur)    
            if not dfs(leftChild[cur]):
                return False
            if not dfs(rightChild[cur]):
                return False
            return True
        
        not_head = set(leftChild + rightChild)
        for i in range(n):
            if i in not_head:
                continue
            return dfs(i) and used == set(range(n))
        return False

1123. Lowest Common Ancestor of Deepest Leaves

LCA Algorithm

# 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 lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

        d = []
        cur_depth = -1
        nodes = {}

        def dfs(cur, his, depth):
            nonlocal cur_depth, d
            nodes[cur.val] = cur
            
            if not cur.left and not cur.right:
                # leaf node
                # print(cur.val, his)
                if cur_depth < depth:
                    cur_depth = depth
                    d = his[:] + [cur.val]
                elif cur_depth == depth:
                    temp = []
                    p = set(his)
                    for i in range(len(d) - 1, -1, -1):
                        value = d[i]
                        if value in p:
                            temp.append(value)
                    d = temp[::-1]
                return

            his.append(cur.val)
            if cur.left:
                dfs(cur.left, his, depth + 1)
            
            if cur.right:
                dfs(cur.right, his, depth + 1)
            his.pop()

        dfs(root, [], 0)
        
        # print(d)
        # print(cur_depth)
        # print(nodes)

        return nodes[d[-1]]