菠菜源码怎么做网站,移动网站有哪些,新东方教育培训机构官网,专门做app的原型网站记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/19 590. N 叉树的后序遍历2/20 105. 从前序与中序遍历序列构造二叉树2/21 106. 从中序与后序遍历序列构造二叉树2/22 889. 根据前序和后序遍历构造二叉树2/23 2583. 二叉…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/19 590. N 叉树的后序遍历2/20 105. 从前序与中序遍历序列构造二叉树2/21 106. 从中序与后序遍历序列构造二叉树2/22 889. 根据前序和后序遍历构造二叉树2/23 2583. 二叉树中的第 K 大层和2/24 2476. 二叉搜索树最近节点查询2/25 235. 二叉搜索树的最近公共祖先 2/19 590. N 叉树的后序遍历 左右根 栈实现 mem记录节点是否已被处理 class Node(object):def __init__(self, valNone, childrenNone):self.val valself.children childrendef postorder(root)::type root: Node:rtype: List[int]st [root]if not root:return []ans []memset()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: TreeNoden 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(iroot1, 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: TreeNodeif 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(iroot1, 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: TreeNodedef create(pre, post):if len(pre)0 or len(post)0:return Nonen len(pre)if n1:return TreeNode(post[0])leftsize post.index(pre[1])1left create(pre[1:1leftsize],post[:leftsize])right create(pre[1leftsize:],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: intimport heapqh []l [root]while l:tmp[]total 0for node in l:totalnode.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)ltmp[:]if len(h)k:return -1return heapq.heappop(h) 2/24 2476. 二叉搜索树最近节点查询 深搜获取节点值 从小到大 二分搜索 class TreeNode(object):def __init__(self, val0, leftNone, rightNone):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 jn else -1if jn or v[j]!q:j-1mn v[j] if j0 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: TreeNodewhile root:v root.valif vp.val and vq.val:root root.rightelif vp.val and vq.val:root root.leftelse:return root
