Binary Tree

Tree's structure is repetitive, huge or tiny tree alike, they are best fit for recursive thinking.

Q: Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]

Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []

Output: []

Example 3:

Input: root = [0]

Output: [0]

S1: 

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:

if not root:

return None

ltail = dfs(root.left)

rtail = dfs(root.right)

if ltail:

ltail.right = root.right

root.right = root.left

root.left = None

return rtail or ltail or root

dfs(root)

#O(n), O(n)

Q: Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]

Output: [-1]

S1: short code with details, try to build left branch first and see what will happen.

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

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

if not inorder:

return None

root = TreeNode(postorder.pop())

index = inorder.index(root.val)

root.right = self.buildTree(inorder[index+1:], postorder)

root.left = self.buildTree(inorder[:index], postorder)

return root

#O(nn), O(n)

S2:

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

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

valToIndx = {v:i for i,v in enumerate(inorder)}

def dfs(l:int, r:int) -> Optional[TreeNode]:

if l > r:

return None

root = TreeNode(postorder.pop())

index = valToIndx[root.val]

root.right = dfs(index+1,r)

root.left = dfs(l,index-1)

return root

return dfs(0, len(inorder)-1)

#O(n), O(n)

Q: Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

S1:

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

if not root:

return None

que = [root]

res = []

while que:

sz = len(que)

tmp = []

for i in range(sz):

cur = que.pop(0)

tmp.append(cur.val)

if cur.left:

que.append(cur.left)

if cur.right:

que.append(cur.right)

res.append(tmp)

return res

#O(n), O(n)

Q:

S1: