微信文档seo基础培训

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

2/19 590. N 叉树的后序遍历

左右根 栈实现
mem记录节点是否已被处理

class Node(object):def __init__(self, val=None, children=None):self.val = valself.children = childrendef postorder(root):""":type root: Node:rtype: List[int]"""st = [root]if not root:return []ans = []mem=set()while st:node = st[-1]if len(node.children)==0 or node in mem:ans.append(node.val)st.pop()continuest.extend(reversed(node.children))mem.add(node)return ans

---

2/20 105. 从前序与中序遍历序列构造二叉树

根据先序遍历 根左右 确定根节点
再根据中序遍历中根节点位置 将左右子树分开

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef buildTree(preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""n = len(inorder)indic = dict(zip(inorder,range(n)))def create(i, j):if i > j: return Noneroot = TreeNode(preorder.pop(0))iroot = indic[root.val]root.left = create(i,iroot-1)root.right = create(iroot+1, j)return rootreturn create(0, n - 1)

---

2/21 106. 从中序与后序遍历序列构造二叉树

根据后序遍历 中序遍历 生成树
从后续遍历最后确定根节点
在中序遍历中 将根节点左右子树分开

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef buildTree(inorder,postorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""if len(postorder)==0 or len(inorder)==0:return Nonen = len(inorder)indic = dict(zip(inorder,range(n)))def create(i, j):if i > j: return Noneroot = TreeNode(postorder.pop())iroot = indic[root.val]root.right = create(iroot+1, j)root.left = create(i, iroot-1)return rootreturn create(0, n - 1)

---

2/22 889. 根据前序和后序遍历构造二叉树

前序 根左右
后续 左右根
前序根后一个为左子树的根 在后续中找到这个根可以划分左右子树

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef constructFromPrePost(preorder, postorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""def create(pre, post):if len(pre)==0 or len(post)==0:return Nonen = len(pre)if n==1:return TreeNode(post[0])leftsize = post.index(pre[1])+1left = create(pre[1:1+leftsize],post[:leftsize])right = create(pre[1+leftsize:],post[leftsize:-1])return TreeNode(pre[0],left,right)return create(preorder,postorder)

---

2/23 2583. 二叉树中的第 K 大层和

BFS 计算每一层的和
最小堆存储最大的K个和

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef kthLargestLevelSum(root, k):""":type root: Optional[TreeNode]:type k: int:rtype: int"""import heapqh = []l = [root]while l:tmp=[]total = 0for node in l:total+=node.valif node.left:tmp.append(node.left)if node.right:tmp.append(node.right)if len(h)<k or h[0]<total:heapq.heappush(h,total)if len(h)>k:heapq.heappop(h)l=tmp[:]if len(h)<k:return -1return heapq.heappop(h)

---

2/24 2476. 二叉搜索树最近节点查询

深搜获取节点值 从小到大
二分搜索

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef closestNodes(root, queries):""":type root: Optional[TreeNode]:type queries: List[int]:rtype: List[List[int]]"""import bisectv = []def dfs(node):if not node:returndfs(node.left)v.append(node.val)dfs(node.right)dfs(root)print(v)n = len(v)ans = []for q in queries:j = bisect.bisect_left(v, q)mx = v[j] if j<n else -1if j==n or v[j]!=q:j-=1mn = v[j] if j>=0 else -1ans.append([mn,mx])return ans

---

2/25 235. 二叉搜索树的最近公共祖先

根据二叉搜索树特性 根节点不可能比两个节点都大 或都小
注意：p,q为节点 不是数值

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef lowestCommonAncestor(root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""while root:v = root.valif v<p.val and v<q.val:root = root.rightelif v>p.val and v>q.val:root = root.leftelse:return root

---