Binary Tree

Summary

There are two patterns for solving binary tree problems:

1. Traversal: Can you solve the problem via traversing the binary tree once?
2. Recursion: Can you define a recursive function and decompose the problem into smaller subproblems?

Understanding Preorder, Inorder, and Postorder Traversal

Preorder, inorder, and postorder represent three specific timestamps during the traversal of a binary tree:

1. Preorder: Code in this position is executed when visiting the node.
2. Inorder: Code in this position is executed after completing the left subtree traversal but before the right subtree traversal.
3. Postorder: Code in this position is executed when leaving the node.

Invert a Binary Tree (Leetcode 226)

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

        if root is None:
            return 

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Populating Next Right Pointers in Each Node (Leetcode 116)

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        self.connect_node(root, None)

        return root


    def connect_node(self, cur, nxt):
        if cur is None:
            return

        cur.next = nxt
        self.connect_node(cur.left, cur.right)
        self.connect_node(cur.right, cur.next.left if cur.next is not None else None)

Flatten Binary Tree to Linked List (Leetcode 114)

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

        temp = root.right
        root.right = root.left
        root.left = None


        p = root

        while p.right is not None:
            p = p.right

        p.right = temp

        return None

Maximum Binary Tree (Leetcode 654)

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:

        if not nums:
            return None
        max_value = -1

        for i, num in enumerate(nums):
            if num > max_value:
                max_value = num
                max_id = i

        root = TreeNode(max_value)
        root.left = self.constructMaximumBinaryTree(nums[:max_id])
        root.right = self.constructMaximumBinaryTree(nums[max_id+1:])

        return root

Construct Binary Tree from Preorder and Inorder Traversal (Leetcode 105)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

        rootNode = preorder[0]

        inorder_dict = {}

        for i, val in enumerate(inorder):
            inorder_dict[val] = i

        return self.build(preorder, inorder, 0, len(preorder)-1, 0, len(inorder)-1, inorder_dict)

    def build(self, preorder, inorder, pre_start, pre_end, in_start, in_end, inorderdict):
        if pre_start > pre_end:
            return None

        root = TreeNode(val=preorder[pre_start])

        inorder_root_id = inorderdict[root.val]

        left_size =  inorder_root_id - in_start

        root.left = self.build(preorder, inorder, pre_start + 1, pre_start + left_size, in_start, in_start + left_size, inorderdict)

        root.right = self.build(preorder, inorder, pre_start + 1 + left_size, pre_end, inorder_root_id+ 1, in_end, inorderdict)

        return root      

Find Duplicate Subtrees (Leetcode 652)

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.sub_tree = {}
        self.res = []
        self.find_subtrees(root)

        return self.res


    def find_subtrees(self, root):

        if root is None:
            return 'none'

        left = self.find_subtrees(root.left)
        right = self.find_subtrees(root.right)

        tree_key = left + '_' + right + '_' + str(root.val)

        freq = self.sub_tree.get(tree_key, 0)

        if freq == 1:
            self.res.append(root)

        self.sub_tree[tree_key] = freq + 1

        return tree_key