Binary Tree
5 min readApr 3, 2020
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
if root is None:return []
if root.left is None and root.right is None:return [root.val]
left, leaf, right = [root.val], [], []
def get_boundary(node, side='left'):
if node is None:return
if side =='left':
if node.left or node.right:left.append(node.val)
if node.left is None:
get_boundary(node.right)
else:
get_boundary(node.left)
else:
if node.left or node.right:right.append(node.val)
if node.right is None:
get_boundary(node.left,'right')
else:
get_boundary(node.right,'right')
def get_leaf(node):
if node is None:return
get_leaf(node.left)
if node.left is None and node.right is None:
leaf.append(node.val)
get_leaf(node.right)
get_boundary(root.left, 'left')
get_leaf(root)
get_boundary(root.right,'right')
return left+leaf+right[::-1]
103. Binary Tree Zigzag Level Order Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if root is None:return []
def bfs():
current_level = [root]
i = 0
while current_level:
new_level = []
if i%2==0:res.append([node.val for node in current_level])
else:res.append([node.val for node in current_level[::-1]])
for node in current_level:
if node.left:
new_level.append(node.left)
if node.right:
new_level.append(node.right)
i+=1
current_level = new_level
bfs()
return res
1008. Construct Binary Search Tree from Preorder Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
def helper(preorder):
if not preorder:return None
if len(preorder)==1:
return TreeNode(preorder[0])
root_val = preorder[0]
left = [val for val in preorder[1:] if val<root_val ]
right = [val for val in preorder[1:] if val>root_val]
left_node = helper(left)
right_node = helper(right)
root = TreeNode(root_val)
root.left = left_node
root.right = right_node
return root
return helper(preorder)
449. Serialize and Deserialize BST
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.
"""
if root is None:return "#"*100
nodes = []
def preorder(node):
if node is None:return
nodes.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
#print(nodes)
return ','.join(nodes)def deserialize(self, data: str) -> TreeNode:
"""Decodes your encoded data to tree.
"""
if data == "#"*100:return None
nodes = data.split(',')
vals = collections.deque()
for node in nodes:
vals.append(int(node))
def build(min_val, max_val):
if vals and min_val < vals[0] < max_val:
val = vals.popleft()
node = TreeNode(val)
node.left = build(min_val, val)
node.right = build(val, max_val)
return node
return None
The above code works
This code is NOT working
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.
"""
if root is None:return "#"*100
nodes = []
def preorder(node):
if node is None:return
nodes.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
#print(nodes)
return ','.join(nodes)def deserialize(self, data: str) -> TreeNode:
"""Decodes your encoded data to tree.
"""
if data == "#"*100:return None
nodes = data.split(',')
def helper(preorder):
if not preorder:return None
if len(preorder)==1:return TreeNode(preorder[0])
root_val = preorder[0]
rest = preorder[1:]
#idx = bisect.bisect_left(rest, root_val)
left = [val for val in rest if val<root_val]
right = [val for val in rest if val>root_val]
root = TreeNode(root_val)
root.left = helper(left)
root.right = helper(right)
return root
return helper(nodes)
236. Lowest Common Ancestor of a Binary Tree
Naive approach
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p is q:return p
if p is root or q is root:return root
dummy = None
parents = {}
found = [False, False]
parents_p = set()
parents_q = set()
def traverse(node, parent=dummy, level=0):
if node is None:return
else:
if node == p:
parents_p.add((level, p))
found[0] = True
elif node == q:
parents_q.add((level, q))
found[1] = True
parents[node] = (level-1, parent)
if found[0] and found[1]:return
traverse(node.left, node, level+1)
traverse(node.right, node, level+1)
traverse(root)
node = p
while node is not None:
parents_p.add(parents[node])
_, node = parents[
node]
node = q
while node is not None:
parents_q.add(parents[node])
_, node = parents[node]
_, lca_node = max(parents_p & parents_q)
return lca_node
A much better one from here
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
if not root: return None
if p == root or q == root:
return root
left = self.lowestCommonAncestor(root.left, p , q)
right = self.lowestCommonAncestor(root.right, p , q)
if left and right:
return root
if not left:
return right
if not right:
return left173. Binary Search Tree Iterator
As for BST, the in order traverse can guarantee the output is in a sorted order. So a naive solution will be inorder traverse and put everything in a stack then pop one item each time.
However, this solution will have a complexity of O(n) during the class instantiation. Hence, it is not a very good design. Although this design, the amortized complexity for next is also O(1), a better design can make the time more uniformly distributed.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass BSTIterator:
def _inorder(self, node):
if node is None:return
self._inorder(node.left)
self._stack.append(node.val)
self._inorder(node.right) def __init__(self, root: TreeNode):
self._stack = []
self._inorder(root)
self._stack = self._stack[::-1] def next(self) -> int:
"""
@return the next smallest number
"""
if self._stack:return self._stack.pop()
else:return -1 def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return len(self._stack)>0# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
A better design from here
class BSTIterator(object):
def __init__(self, root):
self.stack = []
self._extract(root)
def _extract(self, root):
while root:
self.stack.append(root)
root = root.left
def hasNext(self):
return len(self.stack) > 0
def next(self):
node = self.stack.pop()
if node.right:
self._extract(node.right)
return node.val102. Binary Tree Level Order Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if root is None:return []
def bfs():
current_level = [root]
while current_level:
this_res = []
new_level = []
for node in current_level:
if node:this_res.append(node.val)
if node.left:new_level.append(node.left)
if node.right:new_level.append(node.right)
res.append(this_res)
current_level = new_level
bfs()
return res
