1.题目描述

2.思路

二叉树的前序遍历遵循 根左右
（1）方法 preorderTraversal
输入参数: TreeNode root

root是二叉树的根节点。
返回值: List

返回一个包含二叉树节点值的列表，这些值按照前序遍历的顺序排列。
功能:

这个方法是前序遍历的主方法，它创建一个空的List来存储遍历结果。
然后，它调用一个辅助方法preorderHelper，将根节点root和结果列表result传递给它。
最后，返回结果列表result。
（2）输入参数:
TreeNode node: 当前节点。
List result: 用于存储遍历结果的列表。
功能:

这个方法是一个递归方法，用于执行前序遍历。
检查节点是否为空:
如果当前节点node为空，直接返回，不做任何处理。
访问根节点:
如果当前节点不为空，将当前节点的值node.val添加到结果列表result中。
递归遍历左子树:
调用自身preorderHelper，传入当前节点的左子节点和结果列表result，继续遍历左子树。
递归遍历右子树:
调用自身preorderHelper，传入当前节点的右子节点和结果列表result，继续遍历右子树。
工作原理
从根节点开始，将根节点的值添加到结果列表中。
递归地遍历左子树，在每个节点上重复步骤1。
当左子树遍历完成后，递归地遍历右子树，同样在每个节点上重复步骤1。

3.代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
         //TreeNode node 当前节点
        List<Integer> result=new ArrayList<>();
        //用于存储遍历结果的列表。
        preoderHelper(root,result);
        /*功能:

这个方法是前序遍历的主方法，它创建一个空的List<Integer>来存储遍历结果。
然后，它调用一个辅助方法preorderHelper，将根节点root和结果列表result传递给它。
最后，返回结果列表result。*/
        return result;

    }
    private void preoderHelper(TreeNode node,List<Integer> result)
    {
        if(node==null)
        {
            return;
        }
        result.add(node.val);//访问根节点
        preoderHelper(node.left,result);//递归遍历左子树
        preoderHelper(node.right,result);//右子树
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
/*class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        preoderHelper(root,result);
        return result;

    }
    private void preoderHelper(TreeNode node,List<Integer> result)
    {
        if(node==null)
        {
            return;
        }
        result.add(node.val);//访问根节点
        preoderHelper(node.left,result);//递归遍历左子树
        preoderHelper(node.right,result);//右子树
    }
}*/

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        if(root==null)
        {
            return result;
        }

        Stack<TreeNode> stack=new Stack<>();

        stack.push(root);

        while(!stack.isEmpty())
        {
            TreeNode current=stack.pop();
            result.add(current.val);//访问根节点

            //入栈先右后左，出栈先左后右
            if(current.right!=null)
            {
                stack.push(current.right);
            }
            if(current.left!=null)
            {
                stack.push(current.left);
            }
        }
        return result;

    }
}