Leetcode 150

Same Tree

Brute

def preorder(self, node, result):
        if not node:
            result.append(None)
            return
        result.append(node.val)
        self.preorder(node.left, result)
        self.preorder(node.right, result)


def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    p_res = []
    q_res = []

    self.preorder(p, p_res)
    self.preorder(q, q_res)

    return True if p_res == q_res else False

Optimized

def isSameTree(p, q):
    if not p and not q:                # Base case 1
        return True
    if not p or not q:                 # Base case 2
        return False
    if p.val != q.val:                 # Base case 3
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Invert Binary Tree

Brute

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

Optimized

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

Symmetric Tree

Brute

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        stack = [(root.left, root.right)]

        while stack:
            left, right = stack.pop(0)

            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            stack.append((left.left, right.right))
            stack.append((left.right, right.left)) 
        return True

Optimized

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(self, node1, node2):
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            return (t1.val == t2.val) and isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
        return isMirror(root.left, root.right) if root else True

Construct Binary Tree from Preorder and Inorder Traversal

Brute

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        #get root from preorder
        #get left and right subtree from inorder
        if not preorder or not inorder:
            return None
        root = preorder[0] 
        root_node = TreeNode(root)
        index = inorder.index(root)
        root_node.left = self.buildTree(preorder[1:index+1], inorder[:index])
        root_node.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root_node

Optimized

106. Construct Binary Tree from Inorder and Postorder Traversal

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Post L R Ro
        # Pre  L Ro R
        if not postorder or not inorder:
            return None

        root = postorder[-1] 
        root_node = TreeNode(root)
        index = inorder.index(root)
        left_inorder = inorder[:index]
        root_node.left = self.buildTree(left_inorder, postorder[:len(left_inorder)])
        root_node.right = self.buildTree(inorder[index+1:], postorder[len(left_inorder):-1])
        return root_node

Populating Next Right Pointers in Each Node II

from collections import deque
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None

        queue = deque([root])

        while queue:
            size = len(queue)
            prev = None

            for i in range(size):
                node = queue.popleft() 

                if prev:
                    prev.next = node
                prev = node

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)
            prev.next = None
        return root

Flatten Binary Tree to Linked List

def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return

        queue = [root]
        prev = None

        while queue:
            node = queue.pop()

            if prev:
                prev.right = node
            prev = node

            if node.right:
                queue.append(node.right)

            if node.left:
                queue.append(node.left)
                node.left = None
        return root

Average of Levels in Binary Tree

def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            level_sum = 0

            for i in range(level_size):
                node = queue.popleft()
                level_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(level_sum/level_size)
        return result