Algorithm - Tree (3)

Leetcode Tree problem collection (3)

• 99.Recover Binary Search Tree
• 94.Binary Tree Inorder Traversal
• 116.Populating Next Right Pointers in Each Node
• 114.Flatten Binary Tree to Linked List
• 654.Maximum Binary Tree
• 106.Construct Binary Tree from Inorder and Postorder Traversal

Inorder (Left, Root, Right)
Preorder (Root, Left, Right)
Postorder (Left, Right, Root)

99. Recover Binary Search Tree

In-order tranversal in a Binary Search Tree should get an ascending array. So when $Node_i < Node_{i-1}$ means $Node_i$ is the error node. It should swao with either $Node_{i-1}$ or another error node if found.
x, y are pointers of error nodes, pre is used to log the previous node val. node.val shoule always less than pre.val

def recoverTree(self, root: TreeNode) -> None:
    """
    Do not return anything, modify root in-place instead.
    """
    
    def findError(node):
        nonlocal x, y, pre
        if not node:
            return
        
        findError(node.left)
        if pre and node.val < pre.val:
            y = node
            # 1st error
            if not x:
                x = pre
            # 2nd error
            else:
                return
        pre = node
        findError(node.right)
    
    x = y = pre = None
    findError(root)
    x.val, y.val = y.val, x.val

94. Binary Tree Inorder Traversal

Classic in-order search: left - root-right

def inorderTraversal(self, root: TreeNode) -> List[int]:
        
    def traversal(root):
        nonlocal res
        if not root:
            return
        traversal(root.left)
        res.append(root.val)
        traversal(root.right)
    
    res = []
    traversal(root)
    return res

116. Populating Next Right Pointers in Each Node

DFS

def connect(self, root: 'Node') -> 'Node':
    if not root:
        return
    
    # connect local left, right
    if root.left:
        root.left.next = root.right
    
    if root.right and root.next:
        root.right.next = root.next.left
    self.connect(root.left)
    self.connect(root.right)
    return root

BFS / deque

using Deque

from collections import deque
def connect(self, root: 'Node') -> 'Node':
    if not root:
        return root
    
    q = deque([root])
    while q:
        size = len(q)
        while size > 0:
            node = q.popleft()
            if size > 1: ## not the right most:
                node.next = q[0]
            size -= 1
            if node.left:
                q.append(node.left)
                q.append(node.right)
    return root

Or BFS with improvement, get rid of the deque, use the next pointer.

def connect(self, root: 'Node') -> 'Node':
    if not root:
        return root
    
    cur  = root
    next = root.left

    while next :
        cur.left.next = cur.right
        
        # not the right-most node
        if cur.next:
            cur.right.next = cur.next.left
            cur = cur.next
        else:
            # go to the next level
            # start from the left most element
            cur = next
            next = cur.left
    return root

114. Flatten Binary Tree to Linked List

DFS

post-order, flatten left, then flatten right, move left child to right and append the original right child to the end of new right child

def flatten(self, root: TreeNode) -> None:
    """
    Do not return anything, modify root in-place instead.
    """
    if not root:
        return
    self.flatten(root.left)
    self.flatten(root.right)
    
    right = root.right
    left = root.left
    
    root.left = None
    root.right = left
    
    p = root
    while p.right:
        p = p.right
    p.right = right
    return root

Iteration

def flatten(self, root: TreeNode) -> None:
    """
    Do not return anything, modify root in-place instead.
    """
    while root:
        if not root.left:
            root = root.right
        else:
            # find rightest element
            p = root.left
            while p.right:
                p = p.right
            
            # move right child to left.right
            p.right = root.right
            # move left child to right
            root.right = root.left
            root.left = None
            root = root.right

654. Maximum Binary Tree

Classic recursion

def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
    if not nums:
        return None
    val = max(nums)
    i = nums.index(val)
    root = TreeNode(val)
    root.left = self.constructMaximumBinaryTree(nums[:i])
    root.right = self.constructMaximumBinaryTree(nums[i + 1: ])
    return root  

106. Construct Binary Tree from Inorder and Postorder Traversal

Pretty straightforward solution, but not the best!

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
    if not inorder or not postorder:
        return None
    
    val = postorder[-1]
    root = TreeNode(val)
    
    i = inorder.index(val)
    in_left = inorder[:i]
    in_right = inorder[i + 1:]
    
    post_left = postorder[:len(in_left)]
    post_right = postorder[len(in_left): -1]
    
    root.left = self.buildTree(in_left, post_left)
    root.right = self.buildTree(in_right, post_right)
    return root

Finding index is O(n). Slicing array is O(k), k = slicing size. And extra space. Overall time and extra space is O(n^2)
So, to avoid finding index and slicing, use hash map

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        
    dic = {v: i for i, v in enumerate(inorder)}
    
    def build(lo, hi):
        if lo > hi:
            return None
        node = TreeNode(postorder.pop())
        i = dic[node.val]
        
        # poping from post order, so should construct right child first
        node.right = build(i + 1, hi)
        node.left = build(lo, i - 1)
        return node
    
    return build(0, len(inorder) - 1)

And LC105 can be imporved in similar way.