Day 17 of LeetCode

Documenting LeetCode solving.

Q51

572. Subtree of Another Tree

Easy. Tree

Use the same tree problem.

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Both are null or subRoot is null
        if not subRoot:
            return True
        # Don't need to check if subRoot is not null 
        # after the first if condition
        if not root:
            return False

        if self.sameTree(root, subRoot):
            return True

        return (self.isSubtree(root.left, subRoot) or
                self.isSubtree(root.right, subRoot))

    def sameTree(self, s, t):
        if not s and not t:
            return True
        if s and t and s.val == t.val:
            return (self.sameTree(s.left, t.left) and
                    self.sameTree(s.right, t.right))
        return False

Q52

235. Lowest Common Ancestor of a Binary Search Tree

Medium. Tree

Because it's a binary search tree, the LCA will be the split node.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        curr = root

        while curr:
            if p.val > curr.val and q.val > curr.val:
                curr = curr.right
            elif p.val < curr.val and q.val < curr.val:
                curr = curr.left
            # One larger one smaller or equal
            else:
                return curr

Q53

102. Binary Tree Level Order Traversal

Medium. Tree

BFS

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        # Use queue
        q = collections.deque()
        q.append(root)

        while q:
            qLen = len(q)
            level = []
            for i in range(qLen):
                node = q.popleft()
                # Check node != null
                if node:
                    level.append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            # Check level != null
            if level:
                res.append(level)

        return res