Trees and Graphs
2020-01-19 本文已影响0人
inspiredhss
- Validate Binary Search Tree
# Validate Binary Search Tree
# Given a binary tree,
# determine if it is a valid binary search tree (BST).
class Solution:
def isValidBST(self, root): #输入一棵树
output = [] #树放入列表
self.inOrder(root, output)#中序放入
for i in range(1, len(output)):
if output[i-1] >= output[i]:#中序递增即为BST
return False #任一非增 中断False
return True
def inOrder(self, root, output):
if root is None:
return
self.inOrder(root.left, output) #递归调用
output.append(root.val) # 中序 左中右 递增
self.inOrder(root.right, output)#递归调用
- Binary Tree Inorder Traversal
# Binary Tree Inorder Traversal
# Given a binary tree;
# return the inorder traversal of its nodes' values.
class Solution:
def inorderTraversal(self, root):
res, stack = [], [] # 结果、中间数组；
while True:
while root: #可循环其左节点的头结点
stack.append(root) # 存节点
root = root.left # 一直左
if not stack:
return res
node = stack.pop() # 存下最左结点
res.append(node.val) # 存节点值
root = node.right # 左无 其右节点循环左、或存上层左&循环其右
- Binary Tree Level Order Traversal
# Binary Tree Level Order Traversal
# Given a binary tree,
# return the level order traversal of its nodes' values.
# (ie, from left to right, level by level).
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]: #输入数 输出二维数组
if not root:
return []
ans, level = [], [root] # 结果数据集；当前层节点
while level: # 遍历每个当前层节点
ans.append([node.val for node in level]) #归并当前层集level至res
temp = [] # 下层节点集
for node in level: #确定下一层节点集temp
temp.extend([node.left, node.right]) #extend元素添加
level = [leaf for leaf in temp if leaf] # 进入下一层去遍历
return ans
- Binary Tree Zigzag Level Order Traversal
# 103. Binary Tree Zigzag Level Order Traversal
# Given a binary tree,
# return the zigzag level order traversal of its nodes' values.
#(ie, from left to right, then right to left for the next level and alternate between).
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:return []
res, level, direction = [], [root], 1
while level:
res.append([n.val for n in level][::direction])
direction *= -1
level = [kid for node in level for kid in (node.left, node.right) if kid]
return res
- Populating Next Right Pointers in Each Node
## Populating Next Right Pointers in Each Node
# You are given a perfect binary tree
# where all leaves same level, and every parent has two children.
# Populate each next pointer to point to its next right node.
# If there is no next right node, the next pointer should be set to NULL.
import collections
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
Q = collections.deque([root])
while Q:
size = len(Q)
for i in range(size):
node = Q.popleft()
if i < size - 1:
node.next = Q[0] #添加next
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
return root
# Notes:
# deque 是双边队列（double-ended queue），具有队列和栈的性质，在 list 的基础上增加了移动、旋转和增删等
# d = collections.deque([])
# d.append('a') # 在最右边添加一个元素，此时 d=deque('a')
# d.appendleft('b') # 在最左边添加一个元素，此时 d=deque(['b', 'a'])
# d.extend(['c','d']) # 在最右边添加所有元素，此时 d=deque(['b', 'a', 'c', 'd'])
# d.extendleft(['e','f']) # 在最左边添加所有元素，此时 d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
# d.pop() # 将最右边的元素取出，返回 'd'，此时 d=deque(['f', 'e', 'b', 'a', 'c'])
# d.popleft() # 将最左边的元素取出，返回 'f'，此时 d=deque(['e', 'b', 'a', 'c'])
# d.rotate(-2) # 向左旋转两个位置（正数则向右旋转），此时 d=deque(['a', 'c', 'e', 'b'])
# d.count('a') # 队列中'a'的个数，返回 1
# d.remove('c') # 从队列中将'c'删除，此时 d=deque(['a', 'e', 'b'])
# d.reverse() # 将队列倒序，此时 d=deque(['b', 'e', 'a'])
- Populating Next Right Pointers in Each Node
## Populating Next Right Pointers in Each Node
# You are given a perfect binary tree
# where all leaves same level, and every parent has two children.
# Populate each next pointer to point to its next right node.
# If there is no next right node, the next pointer should be set to NULL.
import collections
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
Q = collections.deque([root])
while Q:
size = len(Q)
for i in range(size):
node = Q.popleft()
if i < size - 1:
node.next = Q[0] #添加next
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
return root
# Notes:
# deque 是双边队列（double-ended queue），具有队列和栈的性质，在 list 的基础上增加了移动、旋转和增删等
# d = collections.deque([])
# d.append('a') # 在最右边添加一个元素，此时 d=deque('a')
# d.appendleft('b') # 在最左边添加一个元素，此时 d=deque(['b', 'a'])
# d.extend(['c','d']) # 在最右边添加所有元素，此时 d=deque(['b', 'a', 'c', 'd'])
# d.extendleft(['e','f']) # 在最左边添加所有元素，此时 d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
# d.pop() # 将最右边的元素取出，返回 'd'，此时 d=deque(['f', 'e', 'b', 'a', 'c'])
# d.popleft() # 将最左边的元素取出，返回 'f'，此时 d=deque(['e', 'b', 'a', 'c'])
# d.rotate(-2) # 向左旋转两个位置（正数则向右旋转），此时 d=deque(['a', 'c', 'e', 'b'])
# d.count('a') # 队列中'a'的个数，返回 1
# d.remove('c') # 从队列中将'c'删除，此时 d=deque(['a', 'e', 'b'])
# d.reverse() # 将队列倒序，此时 d=deque(['b', 'e', 'a'])
6.Poputlating Next Right Pointers in Each Node II
# 117. Populating Next Right Pointers in Each Node II
# Given a binary tree
# Populate each next pointer to point to its next right node.
# If there is no next right node, the next pointer should be set to NULL.
# Initially, all next pointers are set to NULL.
class Solution:
def connect(self, root: 'Node') -> 'Node':
old_root = root
prekid = Node(0)
kid = prekid # Let kid point to prekid
while root:
while root:
if root.left:
kid.next = root.left
kid = kid.next
if root.right:
kid.next = root.right
kid = kid.next
root = root.next
root, kid = prekid.next, prekid
kid.next = None # Reset the chain for prekid
return old_root
- Lowest Common Ancestor of a Binary Search Tree
# Lowest Common Ancestor of a Binary Search Tree
class Solution:
# def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# while root:
# if p.val < root.val > q.val:
# root = root.left
# elif p.val > root.val < q.val:
# root = root.right
# else:
# return root
def lowestCommonAncestor(self, root, p, q):
if p.val < root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root
- Lowest Common Ancestor of a Binary Tree
# binary tree==>Lowest Common Ancestor==>
# 236. Lowest Common Ancestor of a Binary Tree
class Solution:
def lowestCommonAncestor(self, root, p, q):
if root in (None, p, q): return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
return root if left and right else left or right
def lowestCommonAncestor(self, root, p, q):
stack = [root]
parent = {root: None}
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
while q not in ancestors:
q = parent[q]
return q
- Given preorder and inorder traversal of a tree, construct the binary tree.
# 105. Construct Binary Tree from Preorder and Inorder Traversal
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[0:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root
- Number of Islands
# Number of Islands
# Given a 2d grid map of '1's (land) and '0's (water),
# count the number of islands.
# An island is surrounded by water;
# formed by connecting adjacent lands horizontally or vertically.
# assume all four edges of the grid are all surrounded by water.
class Solution:
def numIslands(self, grid):
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '#'
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
- Clone Graph
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = []):
self.val = val
self.neighbors = neighbors
"""
# Clone Graph
# Given a reference of a node in a connected undirected graph.
# Return a deep copy (clone) of the graph.
# Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
from collections import deque
class Solution(object):
def cloneGraph(self, node):
if not node:
return node
# Dictionary to save the visited node and it's respective clone
# as key and value respectively. This helps to avoid cycles.
visited = {}
# Put the first node in the queue
queue = deque([node])
# Clone the node and put it in the visited dictionary.
visited[node] = Node(node.val, [])
# Start BFS traversal
while queue:
# Pop a node say "n" from the from the front of the queue.
n = queue.popleft()
# Iterate through all the neighbors of the node
for neighbor in n.neighbors:
if neighbor not in visited:
# Clone the neighbor and put in the visited, if not present already
visited[neighbor] = Node(neighbor.val, [])
# Add the newly encountered node to the queue.
queue.append(neighbor)
# Add the clone of the neighbor to the neighbors of the clone node "n".
visited[n].neighbors.append(visited[neighbor])
# Return the clone of the node from visited.
return visited[node]
