Day 16 of LeetCode

Documenting LeetCode solving.

Q47

104. Maximum Depth of Binary Tree

Easy. Tree

Recursive DFS.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Q48

543. Diameter of Binary Tree

Easy. Tree

Diameter of a node = leftHeight + rightHeight

Height of a node = 1 + max(leftHeightChildNode, rightHeightChildNode)

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0

        def dfs(root):
            # Define nonlocal variable
            nonlocal res

            # Return height
            if not root:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)

            return 1 + max(left, right)

        dfs(root)
        return res

Q49

110. Balanced Binary Tree

Easy. Tree

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        # Return a pair, [balanced?, the height of the node]
        def dfs(root):
            if not root:
                # Base case root == null: balanced, height = 0
                return [True, 0]

            left, right = dfs(root.left), dfs(root.right)
            # balanced? : left subtree, right subtree 
            # and root subtree all should be balanced
            balanced = (left[0] and right[0] and 
                        abs(left[1] - right[1]) <= 1)

            return [balanced, 1 + max(left[1], right[1])]

        return dfs(root)[0]

Q50

100. Same Tree

Easy. Tree

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Base cases are important here

        # p == q == null
        if not p and not q:
            return True
        # p == null or q == null -> p != q
        if not p or not q:
            return False
        # If the first two ifs were not executed,
        # which means p and q are not null
        if p.val != q.val:
            return False

        # Til here p and q are not null and their values are the same

        return (self.isSameTree(p.left, q.left) and 
                self.isSameTree(p.right, q.right))