二叉树先序遍历（递归+迭代）——java

一、题目

leetcode链接： 内容： 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 示例 1： 输入：root = [1,null,2,3] 输出：[1,2,3]

二、先序遍历讲解

（1）下图先序遍历结果： 图1-1：1--2--5--3--7 图1-2：1--2--5--6--3--7 （2）遍历顺序：中左右

图1-1

图1-2

三、先序遍历递归法实现（详解+代码）

1、递归实现讲解：

（1）确定递归放回值以及参数：根据题目需要返回遍历的节点，所以需要List集合存储节点的值，同时需要将二叉树头节点传入； preorder(TreeeNode root,List<Integer> result) （2）确定递归终止条件：遍历二叉树节点为空，表明已经无节点，直接return if(node==null) return; （3）确定递归逻辑：递归顺序为中，左，右，递归开始时，先将根节点添加List集合，然后遍历左子树，最后遍历右子树。 result.add(treeNode.val);//中 preorder(treeNode.left,result); //左 preorder(treeNode.right,result); //右

2、代码实现：

Class test{
     public static void preorder(TreeNode treeNode, List<Integer> result){
        if (treeNode==null){
            return;
        }
        result.add(treeNode.val);//中
        preorder(treeNode.left,result); //左
        preorder(treeNode.right,result); //右
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        preorder(root,result);
        return result;
    }
}

四、先序遍历迭代法实现（详解+代码）

1、迭代法实现讲解

（1）迭代法可以借助栈来进行遍历，栈的结构是后进先出，先进后出； （2）迭代遍历流程如下： ①首先将头节点压入栈，以栈是否为空作为循环条件； ② 栈不为空，弹出栈顶元素添加到集合list，判断右子树是否为空，不为空入栈，判断左子树是否为空，不为空入栈；

2、具体代码实现

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null)
            return list;
        
        Stack<TreeNode> stack=new Stack<>();
        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;
    }