实现二叉树的前序遍历

序遍历的顺序是：先访问根节点，再访问左子树，最后访问右子树。

递归和迭代

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class PreorderTraversal {

    // 递归实现前序遍历
    public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // 访问根节点
        System.out.print(root.val + " ");
        
        // 递归访问左子树
        preorderTraversal(root.left);
        
        // 递归访问右子树
        preorderTraversal(root.right);
    }

    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);

        System.out.println("前序遍历结果：");
        preorderTraversal(root);
    }
}

迭代

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class PreorderTraversal {

    // 递归实现前序遍历
    public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // 访问根节点
        System.out.print(root.val + " ");
        
        // 递归访问左子树
        preorderTraversal(root.left);
        
        // 递归访问右子树
        preorderTraversal(root.right);
    }

    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);

        System.out.println("前序遍历结果：");
        preorderTraversal(root);
    }
}