保定网站建设哪家好,响应式网站和自适应网站的区别,100部禁用app,浏览器最新大全二叉树前序遍历是一种遍历树节点的方式#xff0c;遵循特定的顺序。其基本过程可以总结为以下几个步骤#xff1a;
前序遍历的顺序 访问根节点#xff1a;首先处理当前节点。 递归遍历左子树#xff1a;然后依次访问左子树。 递归遍历右子树#xff1a;最后访问右子树。 …二叉树前序遍历是一种遍历树节点的方式遵循特定的顺序。其基本过程可以总结为以下几个步骤
前序遍历的顺序 访问根节点首先处理当前节点。 递归遍历左子树然后依次访问左子树。 递归遍历右子树最后访问右子树。 这种遍历方式的特点是每次都会先处理根节点再处理左右子树因此叫做“前序”。
例子 考虑下面的二叉树 A/ \B C/ \
D E前序遍历的步骤
访问根节点 A 递归访问左子树 访问 B 递归访问 B 的左子树 访问 D 递归访问 B 的右子树 访问 E 递归访问右子树 访问 C 前序遍历的结果A, B, D, E, C
特点 树的结构前序遍历能够保存树的结构。通过前序遍历的结果可以恢复出原来的树形结构。 适用场景在某些场景下例如复制树或者进行某些类型的树形操作前序遍历是非常有效的。 递归与非递归前序遍历可以通过递归和非递归使用栈两种方式实现。 时间复杂度 前序遍历的时间复杂度为 O(n)其中 n 是树中节点的总数因为每个节点都要被访问一次。
空间复杂度 递归实现的空间复杂度为 O(h)h 是树的高度主要由递归调用栈占用。 非递归实现的空间复杂度也是 O(h)因为栈中存储的节点数不超过树的高度。 下面是二叉树前序遍历的 Java 实现包括递归和非递归两种方式。 递归实现
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val x;}
}import java.util.ArrayList;
import java.util.List;public class PreorderTraversal {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();traverse(root, result);return result;}private void traverse(TreeNode node, ListInteger result) {if (node ! null) {result.add(node.val); // 访问根节点traverse(node.left, result); // 递归左子树traverse(node.right, result); // 递归右子树}}
}2. 非递归实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PreorderTraversalIterative {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null) {return result;}StackTreeNode stack new Stack();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;}
}示例使用 假设有如下的二叉树
// 创建二叉树
TreeNode root new TreeNode(1);
root.left new TreeNode(2);
root.right new TreeNode(3);
root.left.left new TreeNode(4);
root.left.right new TreeNode(5);// 递归遍历
PreorderTraversal pt new PreorderTraversal();
ListInteger result pt.preorderTraversal(root);
System.out.println(result); // 输出: [1, 2, 4, 5, 3]// 非递归遍历
PreorderTraversalIterative pti new PreorderTraversalIterative();
ListInteger resultIterative pti.preorderTraversal(root);
System.out.println(resultIterative); // 输出: [1, 2, 4, 5, 3]
