四川省建设工程造价信息网站,西安网站seo费用,万户网络是干什么的,wordpress文章页的三大标签二叉树的前序遍历问题描述
提供二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。
二叉树的前序遍历是一种深度优先遍历#xff08;DFS#xff09;的方式#xff0c;其遍历顺序为#xff1a;先访问根节点#xff0c;然后递归地对左子树进行前序遍历#xff…二叉树的前序遍历问题描述
提供二叉树的根节点 root 返回它节点值的 前序 遍历。
二叉树的前序遍历是一种深度优先遍历DFS的方式其遍历顺序为先访问根节点然后递归地对左子树进行前序遍历最后递归地对右子树进行前序遍历。
二叉树的定义 在Java中二叉树的定义可以通过一个类表示。以下是一个简单的二叉树节点类的定义
public class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val val;}
}使用这个定义可以构建任意形状的二叉树例如
/** 示例二叉树:* 1* / \* 2 3* / \* 4 5*/
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);这样通过创建不同的TreeNode实例并连接它们的left和right引用可以构建出具体的二叉树结构。
前序遍历的过程
前序遍历的过程是递归的。假设我们有一个二叉树 1/ \2 3/ \4 5前序遍历的顺序是1 - 2 - 4 - 5 - 3
具体步骤如下 访问根节点 从根节点开始首先访问根节点的值。 递归遍历左子树 对根节点的左子树进行前序遍历重复步骤1。 递归遍历右子树 对根节点的右子树进行前序遍历重复步骤1。 整个遍历的顺序是根节点 - 左子树 - 右子树。这个过程是递归的因为对左子树和右子树的遍历过程本质上也是一个前序遍历。
前序遍历的代码实现
import java.util.ArrayList;
import java.util.List;public class BinaryTreePreorderTraversal {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;}// 1. 访问根节点result.add(node.val);// 2. 递归左子树preorder(node.left, result);// 3. 递归右子树preorder(node.right, result);}// 示例public static void main(String[] args) {/** 示例二叉树:* 1* / \* 2 3* / \* 4 5*/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);BinaryTreePreorderTraversal solution new BinaryTreePreorderTraversal();ListInteger result solution.preorderTraversal(root);System.out.println(result); // 输出: [1, 2, 4, 5, 3]}
}
