Binary Tree
- definition: at most two children
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self. right = None
Tree Traverse
- pre-order: 先序遍历 left and then right
def preorder_traversal(self, root):
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if not root:
return
res.append(root.val)
self.helper(root.left, res)
self.helper(root.right, res)
#time O(n)
#space O(h), h is the height of the tree, worst O(n)
- in-order: 中序遍历 left, then self and then right
def helper(self, root, res):
if not root:
return
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
- post-order 略
- Trick: base case usually refers to the None, ChildNode below the leaf node. 叶子的下一层
Blanced binary tree:
-
a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less
image.png
Complete binary tree (same structure as heap):
-
a binary tree in which every level, except possibly the last, is competely filled, as far left as possible
image.png
Binary Search Tree: for every single:
- for every single node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.
- in-order traversal: form an ascending order
Get height
def get_height(root):
if not root:
return 0
left = get_height(root.left)
right = get_height(root.right)
return 1 + max(left, right)
Print Level order
first level
second level
third level
def level(root):
q = [root]
next = []
line = []
while q:
head = q.pop(0)
if head.left:
next.append(head.left)
if head.right:
next.append(head.right)
line.append(head.val)
if not q:
print (line)
if next:
q = next
next = []
line = []
#time O(n)
#space O(max(len(q)))
Flip Upside Down
-
given a binary tree where all the right nodes are either leaf nodes with a sibiling or empty
image.png
def upside_bst(root):
if not root:
return root
if not root.left and not root.right:
return root
left_tree = upside_bst(root.left)
root.left.left = root.right
root.left.right = root
root.left = None
root.right = None
return left_tree
#time O(n)
#space O(h) 用recursion就一定会有新的space
#最后返回的是新的树的root
Homework
leetcode 226 104 110 236 103 109
book： data intensive application
