赞
踩
递归就不写了,写一下迭代法
class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return res = [] cur = root stack = [] while cur or stack: if cur: stack.append(cur) cur = cur.left else: cur = stack.pop() res.append(cur.val) cur = cur.right return res
顺便再写一下前序和后序的迭代法
前序:
class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return st = [root] res = [] # cur = while st: cur = st.pop() res.append(cur.val) if cur.right: st.append(cur.right) if cur.left: st.append(cur.left) return res
后序:
class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return cur = root st = [] prev = None res = [] while st or cur: if cur: st.append(cur) cur = cur.left else: cur = st.pop() #现在需要确定的是是否有右子树,或者右子树是否访问过 #如果没有右子树,或者右子树访问完了,也就是上一个访问的节点是右子节点时 #说明可以访问当前节点 if not cur.right or cur.right == prev: res.append(cur.val) prev = cur cur = None else: st.append(cur) cur = cur.right return res
分解很简单,直接交给递归函数。但是遍历的思路都要会
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ def helper(root): if not root: self.res = max(self.res, self.depth) return self.depth += 1 helper(root.left) helper(root.right) self.depth -= 1 self.depth = 0 self.res = 0 helper(root) return self.res
class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 stack = [(root, 1)] max_depth = 0 while stack: node, depth = stack.pop() if node: max_depth = max(max_depth, depth) if node.right: stack.append((node.right, depth + 1)) if node.left: stack.append((node.left, depth + 1)) return max_depth
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
创建一个函数,传入2个节点,判断是否对称
class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ def check(p, q): if p and q: a = p.val == q.val b = check(p.left, q.right) c = check(p.right, q.left) return a and b and c elif (not p) and (not q): return True else: return False return check(root, root)
class Solution(object): def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ def helper(root): if not root: return 0 l = helper(root.left) r = helper(root.right) d = max(l, r) + 1 self.res = max(self.res, l + r) return d self.res = 0 helper(root) return self.res
class Solution(object): def levelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return q = [root] res = [] while q: sz = len(q) temp = [] for i in range(sz): cur = q.pop(0) temp.append(cur.val) if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) res.append(temp[:]) return res
有序数组,找到mid,nums[mid]是根节点,左边和右边分别是左子树和右子树
class Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ def construct(nums, lo, hi): if lo > hi: return mid = lo + (hi-lo)//2 root = TreeNode(nums[mid]) root.left = construct(nums, lo, mid-1) root.right = construct(nums, mid+1, hi) return root if not nums: return n = len(nums) return construct(nums, 0, n-1)
迭代法写中序遍历
class Solution(object): def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True prev = None st = [] cur = root while st or cur: if cur: st.append(cur) cur = cur.left else: cur = st.pop() if prev and prev.val >= cur.val: return False prev = cur cur = cur.right return True
迭代法遍历,太爽了
class Solution(object): def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ st = [] cur = root i = 0 while st or cur: if cur: st.append(cur) cur = cur.left else: cur = st.pop() i += 1 if i == k: return cur.val cur = cur.right
层序遍历,从右往左
class Solution(object): def rightSideView(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return q = deque() q.append(root) res = [] while q: sz = len(q) res.append(q[0].val) for i in range(sz): cur = q.popleft() if cur.right: q.append(cur.right) if cur.left: q.append(cur.left) return res
class Solution(object): def flatten(self, root): """ :type root: TreeNode :rtype: None Do not return anything, modify root in-place instead. """ if not root: return l = self.flatten(root.left) r = self.flatten(root.right) root.left = None root.right = l node = root while node.right: node = node.right node.right = r return root
class Solution(object): def buildTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ def helper(preorder, prelo, prehi, inorder, inlo, inhi): if prelo > prehi or inlo > inhi: return root_val = preorder[prelo] root_idx = inorder.index(root_val) left_size = root_idx - inlo root = TreeNode(root_val) root.left = helper(preorder, prelo+1, prelo+left_size, inorder, inlo, root_idx-1) root.right = helper(preorder, prelo+left_size+1, prehi, inorder, root_idx+1, inhi) return root n = len(preorder) return helper(preorder, 0, n-1, inorder, 0, n-1)
后序遍历,helper返回以root为开始的路径和的哈希表
class Solution(object): def pathSum(self, root, targetSum): """ :type root: TreeNode :type targetSum: int :rtype: int """ def helper(root): if not root: return {} l = helper(root.left) r = helper(root.right) res = {} for k, v in l.items(): x = root.val + k res[x] = v for k, v in r.items(): x = root.val + k res[x] = res.get(x, 0) + v res[root.val] = res.get(root.val, 0) + 1 self.cnt += res.get(targetSum, 0) return res self.cnt = 0 x = helper(root) return self.cnt
思路:如果一个节点能够在它的左右子树中分别找到 p 和 q,则该节点为 LCA 节点。
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ def helper(root, p, q): if not root: return # 说明p或者q本身就是LCA if root == p or root == q: return root left = helper(root.left, p, q) right = helper(root.right, p, q) if left and right: # 说明p和q一个在左子树,另一个在右子树,root就是LCA return root return left if left else right return helper(root, p, q)
自己ac的hard题目。
class Solution(object): def maxPathSum(self, root): """ :type root: TreeNode :rtype: int """ def helper(root): if not root: return 0 leftMax = helper(root.left) rightMax = helper(root.right) x = max(root.val, root.val+leftMax, root.val+rightMax) self.res = max(self.res, x, root.val+leftMax+rightMax) return x self.res = -1001 helper(root) return self.res
dfs
class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ def dfs(grid, i, j): m, n = len(grid), len(grid[0]) if i < 0 or i >= m or j < 0 or j >= n: return if grid[i][j] == "0": return grid[i][j] = "0" dfs(grid, i+1, j) dfs(grid, i-1, j) dfs(grid, i, j+1) dfs(grid, i, j-1) m, n = len(grid), len(grid[0]) res = 0 for i in range(m): for j in range(n): if grid[i][j] == "1": dfs(grid, i, j) res += 1 return res
来自 作者:nettee的题解
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下,实际上就是求腐烂橘子到所有新鲜橘子的最短路径。要用bfs
一开始,我们找出所有腐烂的橘子,将它们放入队列,作为第 0 层的结点。
然后进行 BFS 遍历,每个结点的相邻结点可能是上、下、左、右四个方向的结点,注意判断结点位于网格边界的特殊情况。
由于可能存在无法被污染的橘子,我们需要记录新鲜橘子的数量。在 BFS 中,每遍历到一个橘子(污染了一个橘子),就将新鲜橘子的数量减一。如果 BFS 结束后这个数量仍未减为零,说明存在无法被污染的橘子
class Solution(object): def orangesRotting(self, grid): """ :type grid: List[List[int]] :rtype: int """ m, n = len(grid), len(grid[0]) q = deque() fresh_cnt = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: fresh_cnt += 1 elif grid[i][j] == 2: q.append((i, j)) res = 0 while fresh_cnt > 0 and q: res += 1 sz = len(q) for i in range(sz): cur = q.popleft() i, j = cur[0], cur[1] if i > 0 and grid[i-1][j] == 1: q.append((i-1, j)) grid[i-1][j] = 2 fresh_cnt -= 1 if i < m-1 and grid[i+1][j] == 1: q.append((i+1, j)) grid[i+1][j] = 2 fresh_cnt -= 1 if j > 0 and grid[i][j-1] == 1: q.append((i, j-1)) grid[i][j-1] = 2 fresh_cnt -= 1 if j < n-1 and grid[i][j+1] == 1: q.append((i, j+1)) grid[i][j+1] = 2 fresh_cnt -= 1 if fresh_cnt == 0: return res else: return -1
自己写的暴力解法:
class Solution(object): def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ d = {} for i in prerequisites: a, b = i[0], i[1] if a not in d: d[a] = [b] else: d[a].append(b) learned = set() while len(learned) < numCourses: L = len(learned) # print(learned, x) for n in range(numCourses): if n not in d: learned.add(n) else: flag = True for x in d[n]: if x not in learned: flag = False break if flag: learned.add(n) # print(learned, x) if len(learned) == L: return False return True
看题解:有向图+bfs。用一个in_degree数组存储每个节点(每节课)的入度,再用一个map d存储每个节点的出度。
每次入度为0的课程入队,bfs的思路。
class Solution(object): def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ d = {} in_degree = [0] * numCourses for i in prerequisites: a, b = i[0], i[1] in_degree[a] += 1 if b not in d: d[b] = [a] else: d[b].append(a) q = deque() for n in range(numCourses): if in_degree[n] == 0: q.append(n) cnt = 0 while q: cur = q.popleft() cnt += 1 if cur in d: for k in d[cur]: in_degree[k] -= 1 if in_degree[k] == 0: q.append(k) return cnt == numCourses
面试大概率不会考,跳过
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。