做那个免费视频网站,潍坊网站建设优化,天津seo推广软件,中国新闻社是事业编制吗一、题目描述
给你二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。 示例 1#xff1a; 输入#xff1a;root [1,null,2,3]
输出#xff1a;[1,2,3]示例 2#xff1a;
输入#xff1a;root []
输出#xff1a;[]示例 3#xff1a;
输入#xff1a;roo…一、题目描述
给你二叉树的根节点 root 返回它节点值的 前序 遍历。 示例 1 输入root [1,null,2,3]
输出[1,2,3]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]示例 4 输入root [1,2]
输出[1,2]示例 5 输入root [1,null,2]
输出[1,2]提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100
二、方法一递归方法
一解题思路
递归方法是最直观的按照前序遍历的顺序递归地访问每个节点
如果当前节点为空返回。访问当前节点将节点的值添加到结果列表中。递归地前序遍历左子树。递归地前序遍历右子树。
二具体代码
import java.util.ArrayList;
import java.util.List;public class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();preorder(root, result);return result;}private void preorder(TreeNode node, ListInteger result) {if (node null) {return;}result.add(node.val); // 访问根节点preorder(node.left, result); // 遍历左子树preorder(node.right, result); // 遍历右子树}
}三时间复杂度和空间复杂度
1. 时间复杂度
原因递归方法访问树中每个节点一次。计算对于具有N个节点的二叉树每个节点都恰好被访问一次。结果时间复杂度为O(N)其中N是二叉树中节点的数量。
2. 空间复杂度
原因递归方法使用栈空间来存储递归调用的信息其大小取决于树的高度。最坏情况如果树完全不平衡每个节点只有左子节点或只有右子节点递归栈的深度将达到N。最好情况如果树是完全平衡的递归栈的深度将是logN。额外空间代码中没有使用除了递归栈以外的额外空间。结果空间复杂度介于O(logN)和O(N)之间取决于树的形状。额外空间复杂度是O(1)。
3. 总结
时间复杂度O(N)空间复杂度O(1)额外空间O(logN)到O(N)递归栈空间
四总结知识点 递归这是一种编程技巧允许函数调用自身。在这个代码中preorder函数会递归地调用自身来遍历二叉树的每个节点。 二叉树遍历代码实现了二叉树的前序遍历这是一种深度优先遍历策略按照“根-左-右”的顺序访问树的节点。 二叉树节点定义代码中使用了TreeNode类来定义二叉树的节点每个节点包含一个整数值val和两个指向其左右子节点的指针left和right。 Java集合框架代码使用了ArrayList来存储遍历的结果。ArrayList是Java集合框架中的一个可调整大小的数组实现用于存储对象列表。 函数参数传递代码中的preorder函数接受一个TreeNode类型的参数和一个ListInteger类型的参数这展示了如何在Java中传递和修改对象引用。 基本语法结构代码包含了基本的Java语法结构如类的定义、方法的定义、条件语句if、返回语句return和列表的添加操作result.add。 递归的基本条件在preorder函数中递归的基本条件是当遇到一个null节点时返回这避免了递归调用的无限循环。 方法重载Solution类中有两个名为preorder的方法但它们的参数列表不同这是Java方法重载的例子。一个方法是公共的用于外部调用另一个方法是私有的作为辅助方法用于递归遍历。
三、方法二迭代方法
一解题思路
迭代方法通常使用栈来模拟递归过程
创建一个空栈将根节点压入栈中。当栈不为空时弹出栈顶元素访问该节点并将其值添加到结果列表中。先将弹出节点的右子节点如果有压入栈中然后将左子节点如果有压入栈中。这样可以保证左子节点先被访问。重复步骤2和3直到栈为空。
二具体代码
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();StackTreeNode stack new Stack();if (root ! null) {stack.push(root);}while (!stack.isEmpty()) {TreeNode node stack.pop();result.add(node.val); // 访问节点if (node.right ! null) {stack.push(node.right); // 右子节点先入栈}if (node.left ! null) {stack.push(node.left); // 左子节点后入栈}}return result;}
}三时间复杂度和空间复杂度
1. 时间复杂度
原因迭代方法访问树中每个节点一次。计算对于具有N个节点的二叉树每个节点都恰好被访问一次。结果时间复杂度为O(N)其中N是二叉树中节点的数量。
2. 空间复杂度
原因迭代方法使用栈空间来存储待访问的节点其大小取决于树的高度。最坏情况如果树完全不平衡每个节点只有左子节点或只有右子节点栈的深度将达到N。最好情况如果树是完全平衡的栈的深度将是logN。结果空间复杂度介于O(logN)和O(N)之间取决于树的形状。
3. 总结
时间复杂度O(N)空间复杂度O(logN)到O(N)
四总结知识点 迭代方法与递归方法不同迭代方法使用栈来模拟递归过程用于遍历二叉树的节点。 栈数据结构代码使用了Stack类来存储待访问的节点。栈是一种后进先出LIFO的数据结构用于在迭代过程中保持节点的访问顺序。 二叉树遍历代码实现了二叉树的前序遍历按照“根-左-右”的顺序访问树的节点。 二叉树节点定义代码中使用了TreeNode类来定义二叉树的节点每个节点包含一个整数值val和两个指向其左右子节点的指针left和right。 Java集合框架代码使用了ArrayList来存储遍历的结果。ArrayList是Java集合框架中的一个可调整大小的数组实现用于存储对象列表。 条件语句代码中的if语句用于检查当前节点是否有左右子节点以便将它们添加到栈中。 循环结构while循环用于在栈不为空的情况下继续遍历二叉树的节点。 基本语法结构代码包含了基本的Java语法结构如类的定义、方法的定义、栈的操作push和pop以及列表的添加操作result.add。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
