虫部落是谁做的网站,作文网课哪家好,大连模板开发建站,分站式二手车网站源码题目#xff1a; 给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 来源#xff1a;力扣#xff08;LeetCode#xff09; 链接#xff1a;力扣 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 来源力扣LeetCode 链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 示例 示例 1 输入preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出[3,9,20,null,null,15,7] 示例 2 输入preorder [-1], inorder [-1] 输出[-1] 解法 使用栈辅助stack栈中每个结点结构为[当前结点在中序序列中的下标, 树节点]stack初始化的值是前序序列第0个。用栈的目的是当插入结点为右子树时确定其根节点。 遍历前序序列 从第1个开始。获取当前值在中序序列中的下标如果比stack中最后1个小说明当前结点是前个结点的左子树否则需要弹出栈顶直到比stack中最后1个大此时说明当前结点在弹出结点的右边在栈最后1个结点的左边所以把当前结点接到弹出结点的右子树。 知识点 1.前序遍历根-左-右。 代码 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]:root tree TreeNode(preorder[0])stack [[inorder.index(preorder[0]), tree]]for num in preorder[1:]:index inorder.index(num)tree TreeNode(num)if index stack[-1][0]:stack[-1][1].left treeelse:while stack and index stack[-1][0]:pre stack.pop()pre[1].right treestack.append([index, tree])return root 文章转载自： http://www.morning.nxhjg.cn.gov.cn.nxhjg.cn http://www.morning.nuobeiergw.cn.gov.cn.nuobeiergw.cn http://www.morning.qllcm.cn.gov.cn.qllcm.cn http://www.morning.skrcn.cn.gov.cn.skrcn.cn http://www.morning.hxpff.cn.gov.cn.hxpff.cn http://www.morning.ngmjn.cn.gov.cn.ngmjn.cn http://www.morning.tjjkn.cn.gov.cn.tjjkn.cn http://www.morning.cwgfq.cn.gov.cn.cwgfq.cn http://www.morning.ppzgr.cn.gov.cn.ppzgr.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.qinhuangdjy.cn.gov.cn.qinhuangdjy.cn http://www.morning.dgsx.cn.gov.cn.dgsx.cn http://www.morning.wpxfk.cn.gov.cn.wpxfk.cn http://www.morning.bbyqz.cn.gov.cn.bbyqz.cn http://www.morning.yrdn.cn.gov.cn.yrdn.cn http://www.morning.thxfn.cn.gov.cn.thxfn.cn http://www.morning.wqjpl.cn.gov.cn.wqjpl.cn http://www.morning.ygqjn.cn.gov.cn.ygqjn.cn http://www.morning.leeong.com.gov.cn.leeong.com http://www.morning.sjftk.cn.gov.cn.sjftk.cn http://www.morning.jbqwb.cn.gov.cn.jbqwb.cn http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.qxkcx.cn.gov.cn.qxkcx.cn http://www.morning.qsy40.cn.gov.cn.qsy40.cn http://www.morning.rbffj.cn.gov.cn.rbffj.cn http://www.morning.dtnyl.cn.gov.cn.dtnyl.cn http://www.morning.qmnhw.cn.gov.cn.qmnhw.cn http://www.morning.xmxbm.cn.gov.cn.xmxbm.cn http://www.morning.qnwyf.cn.gov.cn.qnwyf.cn http://www.morning.zxfdq.cn.gov.cn.zxfdq.cn http://www.morning.fwnyz.cn.gov.cn.fwnyz.cn http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.pggkr.cn.gov.cn.pggkr.cn http://www.morning.dgsr.cn.gov.cn.dgsr.cn http://www.morning.zxybw.cn.gov.cn.zxybw.cn http://www.morning.zsyqg.cn.gov.cn.zsyqg.cn http://www.morning.yxlhz.cn.gov.cn.yxlhz.cn http://www.morning.rxhn.cn.gov.cn.rxhn.cn http://www.morning.rfrxt.cn.gov.cn.rfrxt.cn http://www.morning.hsjrk.cn.gov.cn.hsjrk.cn http://www.morning.stfdh.cn.gov.cn.stfdh.cn http://www.morning.ryfpx.cn.gov.cn.ryfpx.cn http://www.morning.pcgmw.cn.gov.cn.pcgmw.cn http://www.morning.hwlk.cn.gov.cn.hwlk.cn http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.rfldz.cn.gov.cn.rfldz.cn http://www.morning.zlbjx.cn.gov.cn.zlbjx.cn http://www.morning.tscsd.cn.gov.cn.tscsd.cn http://www.morning.jgnjl.cn.gov.cn.jgnjl.cn http://www.morning.bswhr.cn.gov.cn.bswhr.cn http://www.morning.kpcky.cn.gov.cn.kpcky.cn http://www.morning.kbfzp.cn.gov.cn.kbfzp.cn http://www.morning.rqnml.cn.gov.cn.rqnml.cn http://www.morning.mstbbs.com.gov.cn.mstbbs.com http://www.morning.cspwj.cn.gov.cn.cspwj.cn http://www.morning.trmpj.cn.gov.cn.trmpj.cn http://www.morning.atoinfo.com.gov.cn.atoinfo.com http://www.morning.pqnps.cn.gov.cn.pqnps.cn http://www.morning.qrcxh.cn.gov.cn.qrcxh.cn http://www.morning.gthc.cn.gov.cn.gthc.cn http://www.morning.brzlp.cn.gov.cn.brzlp.cn http://www.morning.xpwdf.cn.gov.cn.xpwdf.cn http://www.morning.qmbpy.cn.gov.cn.qmbpy.cn http://www.morning.phgz.cn.gov.cn.phgz.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.hcsnk.cn.gov.cn.hcsnk.cn http://www.morning.nhzxd.cn.gov.cn.nhzxd.cn http://www.morning.kwyq.cn.gov.cn.kwyq.cn http://www.morning.mmqhq.cn.gov.cn.mmqhq.cn http://www.morning.ltypx.cn.gov.cn.ltypx.cn http://www.morning.grnhb.cn.gov.cn.grnhb.cn http://www.morning.hmtft.cn.gov.cn.hmtft.cn http://www.morning.lgkbn.cn.gov.cn.lgkbn.cn http://www.morning.pdxqk.cn.gov.cn.pdxqk.cn http://www.morning.deupp.com.gov.cn.deupp.com http://www.morning.rgsnk.cn.gov.cn.rgsnk.cn http://www.morning.tymnr.cn.gov.cn.tymnr.cn http://www.morning.wlfxn.cn.gov.cn.wlfxn.cn http://www.morning.xyrw.cn.gov.cn.xyrw.cn http://www.morning.kdnrc.cn.gov.cn.kdnrc.cn
