Day 19 of LeetCode

Documenting LeetCode solving.

Q57

230. Kth Smallest Element in a BST

Medium. Tree

Iteratively traverse the tree. Go all the way to the left while adding nodes to the stack, if the curr becomes null, means the previous node is the smallest currently. We pop it and n += 1.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        n = 0
        stack = []
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left

            curr = stack.pop()
            n += 1
            if n == k:
                return curr.val
            curr = curr.right

Q58

105. Construct Binary Tree from Preorder and Inorder Traversal

Medium. Tree

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None

        # First item in preorder will always be the root of current subtree
        root = TreeNode(preorder[0])
        # Get the position of the root in inorder
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1 : mid + 1], inorder[ : mid])
        root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 : ])

        return root

Q59

124. Binary Tree Maximum Path Sum

Hard. Tree

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = [root.val]

        # Return max path sum without split
        def dfs(root):
            if not root:
                return 0

            leftMax = dfs(root.left)
            rightMax = dfs(root.right)
            # Can be negative
            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            # Update max path sum with split
            res[0] = max(res[0], root.val + leftMax + rightMax)

            return root.val + max(leftMax, rightMax)

        dfs(root)
        return res[0]