[骨骼清奇]n-array tree, 给一个node 算出包括这个node在内的所有child的sum
[骨骼清奇]n-array tree，给一个node 打印出从这node出发的所有path. 问了时间复杂度和空间复杂度。
[骨骼清奇]第一轮问了两题，第一题是一个数组，在某个位置前元素单调递增，然后单调递减，就是那种元素大小像山一样形状的数组，然后求最大最小值，用binary search做，然后第二题是比较二叉树是否相同，问了一下时间复杂度。
[骨骼清奇]Write a function to detect if two trees are isomorphic.
给定两颗树，判断它们是否有相同的shape.
follow up：如果允许树的节点拥有任意数目的父节点，如何判断？
Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.
def isIsomorphic(n1, n2):
if n1 is None and n2 is None:
return True
if n1 is None or n2 is None:
return False
if n1.data != n2.data :
return False
# Case 1: subtrees NOT "Flipped".
# Case 2: subtrees "Flipped"
return ((isIsomorphic(n1.left, n2.left)and
isIsomorphic(n1.right, n2.right)) or
(isIsomorphic(n1.left, n2.right) and
isIsomorphic(n1.right, n2.left))
)
Time Complexity: The above solution does a traversal of both trees. So time complexity is O(m + n) where m and n are number of nodes in given trees.
Follow up: general tree?
If swap with either two siblings, then we can compare level by level using permutation of node values.
LC 226 Invert Binary Tree 二叉树的镜像（Symmetric Tree）
Recursion:
class Solution:
def Mirror(self, root):
if root == None:
return
self.Mirror(root.left)
self.Mirror(root.right)
root.left,root.right = root.right,root.left
Iterative way:
The idea is that we need to swap the left and right child of all nodes in the tree. So we create a queue to store nodes whose left and right child have not been swapped yet. Initially, only the root is in the queue. As long as the queue is not empty, remove the next node from the queue, swap its children, and add the children to the queue. Null nodes are not added to the queue. Eventually, the queue will be empty and all the children swapped, and we return the original root.
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return root
level=[root]
while level:
for node in level:
node.left,node.right = node.right,node.left
level = [kid for node in level for kid in (node.left,node.right) if kid]
return root
LC 102Binary Tree Level Order Traversal
class Solution:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
ans,level = [],[root]
while level:
ans.append([node.val for node in level])
level = [ kid for n in level for kid in (n.left,n.right) if kid]
return ans
LC 105. Construct Binary Tree from Preorder and Inorder Traversal
class Solution:
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if inorder:
root_ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[root_ind])
root.left = self.buildTree(preorder, inorder[0:root_ind])
#preorder now only contains nodes in right sub-tree of root
root.right = self.buildTree(preorder, inorder[root_ind+1:])
return root
LC 106. Construct Binary Tree from Inorder and Postorder Traversal
class Solution:
def buildTree(self, inorder, postorder):
if inorder:
root_ind = inorder.index(postorder.pop())
root = TreeNode(inorder[root_ind])
root.right = self.buildTree(inorder[root_ind+1:],postorder)
root.left = self.buildTree(inorder[:root_ind],postorder)
return root
[骨骼清奇] LC 96 Unique Binary Search Trees
转移关系：1到n中选定某个i作为root！
class Solution: #beat 100%
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n<1: return 0
F = [0]*(n+1)
F[0] = F[1] = 1
for i in range(2,n+1):
for j in range(i):
F[i] += F[j]*F[i-j-1]
return F[n]
LC95 unique binary search tree II
需要返回所有不同BST的根节点list. 用Recursion做。
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
def generate_trees(start, end):
if start > end:
return [None,]
all_trees = []
for i in range(start, end + 1): # pick up a root
# all possible left subtrees if i is choosen to be a root
left_trees = generate_trees(start, i - 1)
# all possible right subtrees if i is choosen to be a root
right_trees = generate_trees(i + 1, end)
# connect left and right subtrees to the root i
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
all_trees.append(current_tree)
return all_trees
return generate_trees(1, n) if n else []
[骨骼清奇] LC 834 Sum of Distances in Tree
Input: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Nodes的数值是0-N-1，构成一颗树，ans[i]表示从i出发到其他所有nodes的edges数之和。ans[0] = 1+1+2+2+2 = 8
重点是找到关系edge AB在最终答案里的关系：ans[B] = ans[A] + Nodes_A - Nodes_B。因为AB是直接相连的，那么从B出发，对于以B为根节点的nodes而言，ans[A]里面每一个都多加了1，那个1就是edgeAB，因此要减掉Nodes_B。同样的，ans[A]还需要加上Nodes_A, 因为从B出发需要经过BA，而从A出发不用。
class Solution:
def sumOfDistancesInTree(self, N, edges):
"""
:type N: int
:type edges: List[List[int]]
:rtype: List[int]
"""
graph = self.buildGraph(N,edges)
seen = set()
cnts = [1]*N
dist = [0]*N
self.dfs(graph,0,dist,cnts,seen)
#dist[0] is the chosen root and it is answered now!
seen = set()
self.dfs2(graph,0,dist,cnts,seen,N)
return dist
def buildGraph(self,N,edges):
from collections import defaultdict
graph = defaultdict(list)
for i,j in edges:
graph[i].append(j)
graph[j].append(i)
return graph
def dfs(self,graph,i,dist,cnts,seen):
seen.add(i)
for j in graph[i]:
if j in seen:continue
self.dfs(graph,j,dist,cnts,seen)
cnts[i] += cnts[j]
dist[i] += dist[j] + cnts[j]
#cnts[j] means node i is one edge further
def dfs2(self,graph,i,dist,cnts,seen,n):
seen.add(i)
for j in graph[i]:
if j in seen:continue
dist[j] = dist[i] - cnts[j] + (n - cnts[j])
self.dfs2(graph,j,dist,cnts,seen,n)
https://blog.csdn.net/tinkle181129/article/details/79326023
[Uber] LC 314 Binary Tree Vertical Order Traversal
分析：如何判断nodes属于同一层vertical Order？其实是相对于root这个symmetric axis的位置，只要turn right就加一，turn left减一，再把这个表示相对位置的Index放入一个hash table，然后按照index从小打到输出即可！
from collections import deque, defaultdict
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
table = defaultdict(list)
queue = deque()
# put node and the level that it belongs to
queue.append((root, 0))
Gmin = Gmax = 0
while queue:
node, index = queue.popleft()
if index<Gmin:Gmin = index
if index>Gmax:Gmax = index
table[index].append(node.val)
if node.left:
queue.append((node.left, index-1))
if node.right:
queue.append((node.right, index+1))
# The keys of the table are the indices, sort it min to max
# return [table[index] for index in sorted(table)]
return [table[index] for index in range(Gmin,Gmax+1)]
LC 101 Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
General Tree:
left = arr[:len(arr)//2]
right = arr[:len(left):-1]
[骨骼清奇]考察二叉树，自己定义tree node，然后自己把二叉树各种遍历方法写一下，递归的和非递归的。
LC 94 Binary Tree Inorder Traversal
Recursion:
def inorderTraversal1(self, root):
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
Iterative (stack)：从root出发，left child不停的入栈，直到遇到一个Node没有left child(可能是leaf也可能不是)，这就是我们in-order traversal的第一站，然后以它的left child作为root，重复刚刚那一套流程。For each leaf, its left null child will help print the value of itself, and its null right child will help print the correspondent successor (could be an ancestor far above).
class Solution:
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stk = []
ans = []
node = root
while (node is not None) or stk: # empty lists are falsy
if node is not None:
stk.append(node)
node = node.left
else:
node = stk.pop()
ans.append(node.val)
node = node.right
return ans
LC 230 Kth Smallest Element in a BST
class Solution:
def kthSmallest(self, root, k):
self.k = k
self.in_order(root)
return self.result
def in_order(self, node):
if not node:
return None
self.in_order(node.left)
self.k -= 1
if self.k == 0:
self.result=node.val
return
self.in_order(node.right)
Iterative:
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
cnt,stack = 0,[]
node = root
while node is not None or stack:
if node is not None:
stack.append(node)
node=node.left
else:
node=stack.pop()
cnt += 1
if cnt==k: return node.val
node=node.right
LC 144 Binary Tree Preorder Traversal
Beat 100%
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans,stack = [],[]
node = root
while node is not None or stack:
if node is not None:
ans.append(node.val)
#get value before going to children
stack.append(node)
node = node.left
else:
node = stack.pop()
node=node.right
return ans
LC 145 Binary Tree Postorder Traversal
class Solution:
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans,stack = [],[]
node = root
while node is not None or stack:
if node is not None:
#ans.insert(0,node.val) #reverse preorder
ans.append(node.val)
stack.append(node)
node = node.right #reverse preorder
else:
node = stack.pop()
node = node.left #reverse preorder
return ans[::-1]
[Uber]LC 450 Delete Node in a BST
1.When found the node, put right child of the node to the right of [the right most leaf node of left child][max value of left sub-tree but still smaller then any value in right sub tree]. That way the values are still in order.
2.Return the left child of the node(skip root, a.k.a delete it). If the node doesn't have left child, return right child.
3.Otherwise do binary search. If key < root.val, change left child to the returned new root. Do right child if key > root.val.
This solution always runs in O(log(n)) time since when it finds the node to delete, it goes to the right most leaf of the left sub-tree to put right sub-tree of the node there.
Modify and not return any node in recursion, beat 100%!
class Solution:
def deleteNode(self, root, key):
dummy = TreeNode(float('INF'))
dummy.left = root
self.replace(dummy,root,key)
return dummy.left
def replace(self,prev,cur,key):
if not cur: return
if cur.val<key:
self.replace(cur,cur.right,key)
elif cur.val>key:
self.replace(cur,cur.left,key)
else:#FOUND
if cur.left:
left_right_most = cur.left
while left_right_most.right:
left_right_most = left_right_most.right
left_right_most.right=cur.right
if prev.val<key:
prev.right = cur.left or cur.right
else:
prev.left = cur.left or cur.right
Slower Version without prev
class Solution(object):
def deleteNode(self, root, key):
if not root: return None
if root.val == key:
if root.left:
# Find the right most leaf of the left sub-tree
left_right_most = root.left
while left_right_most.right:
left_right_most = left_right_most.right
# Attach right child to the right of that leaf
left_right_most.right = root.right
# Return left child instead of root, a.k.a delete root
return root.left
else:
return root.right
# If left or right child got deleted, the returned root is the child of the deleted node.
elif root.val > key:
root.left = self.deleteNode(root.left, key)
else:
root.right = self.deleteNode(root.right, key)
return root
[GoogleCall]Delete Treenode, all are put in an array. parent 0 has children 1 and 2.
LC 428 N-ary tree
