用java实现二叉树的前序遍历（递归和迭代）

目录

1.题目内容

2.用递归实现前序遍历

2.1解题思路

2.2代码

3.用迭代实现前序遍历

3.1解题思路

3.2代码

1.题目内容

给你二叉树的根节点 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]

2.用递归实现前序遍历

2.1解题思路

前序遍历的顺序为根左右。当根为空时，直接返回null；当根不为空时，先输出根节点，再递归的遍历左子树，最后再递归的遍历右子树。

图解（结合代码看）

2.2代码

public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

3.用迭代实现前序遍历

3.1解题思路

前序遍历的顺序为根左右，我们可以先创建一个栈stack用来存放节点，先将根节点入栈，然后打印根节点的数据。栈是先进后出的结构，所以先入右子树，然后左子树，打印则优先左子树，再打印右子树。当所有节点遍历一遍后，栈为空，结束打印。

 如上图，先将根节点1入栈，此时stack不为空，前序遍历先将根节点出栈打印。再将右子树2入栈。

左子树为空，所以2出栈打印。以2为节点的右子树为空，左子树入栈。

 以3为节点的左右子树都为空，将3出栈打印。此时栈为空，结束遍历。

3.2代码

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer>list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Deque<TreeNode>stack=new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();//出栈顶元素
            list.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return list;
    }