龙武工会网站怎么做,绍兴网站制作工具,北海网站网站建设,哈尔滨网页设计公司题目 给定一棵二叉树的根节点 root #xff0c;返回它节点值的前序遍历。 示例 1#xff1a;
输入#xff1a;root [1,null,2,3]
输出#xff1a;[1,2,3] 示例 2#xff1a;
输入#xff1a;root []
输出#xff1a;[] 示例 3#xff1a;
输入#xff1a;root […题目 给定一棵二叉树的根节点 root 返回它节点值的前序遍历。 示例 1
输入root [1,null,2,3]
输出[1,2,3] 示例 2
输入root []
输出[] 示例 3
输入root [1]
输出[1] 基础知识 二叉树属于一种常用的数据结构是一个由零个或多个节点组成的层次结构。二叉树具有以下特征 1、每个节点最多有两个子节点分别称为左子节点和右子节点。 2、根节点位于树的最顶端没有父节点。 3、叶子节点没有子节点。 4、非叶子节点至少有一个子节点。 前序遍历是二叉树遍历的一种方式其顺序遵循“根节点 - 左子树 - 右子树”的原则。具体步骤如下 1、访问当前节点首先处理当前节点打印节点值或进行其他操作。 2、递归地遍历左子树然后对当前节点的左子树进行前序遍历。 3、递归地遍历右子树最后对当前节点的右子树进行前序遍历。 假如我们有以下的二叉树则其前序遍历的顺序为1 - 2 - 4 - 5 - 3。 1/ \2 3/ \
4 5 递归法 对于给定的二叉树我们可以通过递归的方式来实现前序遍历。下面我们给出了用递归法解题的示例代码具体的解题步骤如下。 1、binary_tree_traversal_recursive 函数接收一个 TreeNode 类型的参数 root它代表二叉树的根节点。函数内部定义了另一个名为 dfs 的辅助函数该函数负责实际的递归遍历工作。 2、在 dfs 函数中我们先访问当前节点然后递归访问左子树最后递归访问右子树。 3、遍历完成后所有节点都已访问dfs 函数逐级返回最终 binary_tree_traversal_recursive 函数返回结果列表 result。
from typing import Listclass TreeNode:def __init__(self, val 0, left None, right None):self.val valself.left leftself.right rightdef binary_tree_traversal_recursive(root: TreeNode) - List[int]:result []def dfs(node):if node is None:return# 访问当前节点result.append(node.val)# 递归访问左子树dfs(node.left)# 递归访问右子树dfs(node.right)dfs(root)return resultright TreeNode(2)
root TreeNode(1, None, right)
right.left TreeNode(3)
result binary_tree_traversal_recursive(root)
print(result) 迭代法 迭代法实现二叉树的前序遍历关键在于利用栈来模拟递归的过程确保节点的访问顺序符合“根节点 - 左子树 - 右子树”的规则。使用迭代法求解本题的主要步骤如下。 1、初始化。创建一个栈并将根节点压入栈中。同时创建一个结果列表用于存放遍历结果。 2、循环处理。当栈不为空时执行以下操作 1弹出栈顶元素。将栈顶元素弹出并将其值添加到结果列表中这是因为前序遍历先访问根节点。 2处理右子树。如果当前节点有右子节点将右子节点压入栈中。这是因为右子节点应当在其左子树访问完后再访问故右子节点应最后处理。 3处理左子树。如果当前节点有左子节点将左子节点压入栈中。这是因为左子节点应在当前节点的右子节点之前访问。 3、结束条件。当栈为空时所有节点都被访问过遍历结束。 根据上面的算法步骤我们可以得出下面的示例代码。
from typing import Listdef binary_tree_traversal_iteration(root: TreeNode) - List[int]:if not root:return []stack, result [root, ], []while stack:# 弹出栈顶元素并访问node stack.pop()if node:# 访问栈顶节点result.append(node.val)# 栈顶元素出栈后先压右子节点保证右子节点最后访问if node.right:stack.append(node.right)# 然后压左子节点if node.left:stack.append(node.left)return resultright TreeNode(2)
root TreeNode(1, None, right)
right.left TreeNode(3)
result binary_tree_traversal_iteration(root)
print(result) 总结 递归法的时间复杂度为O(n)每个节点被访问一次。空间复杂度最好情况下为O(log n)此时为平衡树最坏情况下为O(n)此时为高度为n的斜树。递归法的实现直观反映了前序遍历的逻辑即“根-左-右”但存在栈溢出、空间复杂度较高等缺点。 迭代法的时间复杂度也为O(n)每个节点被访问一次。空间复杂度为O(h)其中h是树的高度。对于平衡树来说为O(log n)最坏情况下高度为n的斜树为O(n)。相较于递归法迭代法使用显式栈管理空间复杂度更加可控。此外迭代法没有递归调用栈的限制适用于处理大规模或深度极大的二叉树。
文章转载自： http://www.morning.pdxqk.cn.gov.cn.pdxqk.cn http://www.morning.qmqgx.cn.gov.cn.qmqgx.cn http://www.morning.lkcqz.cn.gov.cn.lkcqz.cn http://www.morning.ngdkn.cn.gov.cn.ngdkn.cn http://www.morning.pdbgm.cn.gov.cn.pdbgm.cn http://www.morning.dnmgr.cn.gov.cn.dnmgr.cn http://www.morning.tkryt.cn.gov.cn.tkryt.cn http://www.morning.zqwp.cn.gov.cn.zqwp.cn http://www.morning.kjfqf.cn.gov.cn.kjfqf.cn http://www.morning.lskyz.cn.gov.cn.lskyz.cn http://www.morning.bzlfw.cn.gov.cn.bzlfw.cn http://www.morning.rnmdp.cn.gov.cn.rnmdp.cn http://www.morning.wnkbf.cn.gov.cn.wnkbf.cn http://www.morning.xpgwz.cn.gov.cn.xpgwz.cn http://www.morning.zpnfc.cn.gov.cn.zpnfc.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.wpjst.cn.gov.cn.wpjst.cn http://www.morning.ykwqz.cn.gov.cn.ykwqz.cn http://www.morning.kgxyd.cn.gov.cn.kgxyd.cn http://www.morning.ljsxg.cn.gov.cn.ljsxg.cn http://www.morning.ndxrm.cn.gov.cn.ndxrm.cn http://www.morning.thpzn.cn.gov.cn.thpzn.cn http://www.morning.xjpnq.cn.gov.cn.xjpnq.cn http://www.morning.zkqjz.cn.gov.cn.zkqjz.cn http://www.morning.ldqrd.cn.gov.cn.ldqrd.cn http://www.morning.qhmql.cn.gov.cn.qhmql.cn http://www.morning.qpqwb.cn.gov.cn.qpqwb.cn http://www.morning.mmclj.cn.gov.cn.mmclj.cn http://www.morning.bpmdn.cn.gov.cn.bpmdn.cn http://www.morning.lhrxq.cn.gov.cn.lhrxq.cn http://www.morning.cftkz.cn.gov.cn.cftkz.cn http://www.morning.dpbdq.cn.gov.cn.dpbdq.cn http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.rlhgx.cn.gov.cn.rlhgx.cn http://www.morning.qtltg.cn.gov.cn.qtltg.cn http://www.morning.qfcnp.cn.gov.cn.qfcnp.cn http://www.morning.ckrnq.cn.gov.cn.ckrnq.cn http://www.morning.gyfhk.cn.gov.cn.gyfhk.cn http://www.morning.ynjhk.cn.gov.cn.ynjhk.cn http://www.morning.benqc.com.gov.cn.benqc.com http://www.morning.cfpq.cn.gov.cn.cfpq.cn http://www.morning.jbmbj.cn.gov.cn.jbmbj.cn http://www.morning.svtxeu.com.gov.cn.svtxeu.com http://www.morning.kfjnx.cn.gov.cn.kfjnx.cn http://www.morning.lpzyq.cn.gov.cn.lpzyq.cn http://www.morning.rhmt.cn.gov.cn.rhmt.cn http://www.morning.lpsjs.com.gov.cn.lpsjs.com http://www.morning.lxbml.cn.gov.cn.lxbml.cn http://www.morning.fhjnh.cn.gov.cn.fhjnh.cn http://www.morning.kscwt.cn.gov.cn.kscwt.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.jzykq.cn.gov.cn.jzykq.cn http://www.morning.kqpxb.cn.gov.cn.kqpxb.cn http://www.morning.kpmxn.cn.gov.cn.kpmxn.cn http://www.morning.qyrnp.cn.gov.cn.qyrnp.cn http://www.morning.crhd.cn.gov.cn.crhd.cn http://www.morning.c7623.cn.gov.cn.c7623.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.kyjpg.cn.gov.cn.kyjpg.cn http://www.morning.thzwj.cn.gov.cn.thzwj.cn http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.mbaiwan.com.gov.cn.mbaiwan.com http://www.morning.mzhhr.cn.gov.cn.mzhhr.cn http://www.morning.jcfqg.cn.gov.cn.jcfqg.cn http://www.morning.tnfyj.cn.gov.cn.tnfyj.cn http://www.morning.fydsr.cn.gov.cn.fydsr.cn http://www.morning.wnbqy.cn.gov.cn.wnbqy.cn http://www.morning.stwxr.cn.gov.cn.stwxr.cn http://www.morning.ailvturv.com.gov.cn.ailvturv.com http://www.morning.srrrz.cn.gov.cn.srrrz.cn http://www.morning.symgk.cn.gov.cn.symgk.cn http://www.morning.ndtmz.cn.gov.cn.ndtmz.cn http://www.morning.qpmwb.cn.gov.cn.qpmwb.cn http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.tdmgs.cn.gov.cn.tdmgs.cn http://www.morning.jjxnp.cn.gov.cn.jjxnp.cn http://www.morning.btqqh.cn.gov.cn.btqqh.cn
