题解 | #二叉树的前序遍历--递归、非递归#

• 二叉树的前序遍历就是深度优先遍历

递归算法

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public int[] preorderTraversal (TreeNode root) {
        //二叉树前序遍历就是深度优先遍历
        List<Integer> list=new ArrayList<>();
        dfs(list,root);
        int[] res=new int[list.size()];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        return res;
    }
    //递归,先输出根节点，再依次遍历左子树、右子树
    public void dfs(List<Integer> list,TreeNode root){
        if(root!=null){
            list.add(root.val);
            dfs(list,root.left);
            dfs(list,root.right);
        }

    }
}

非递归算法

思路：用栈，先将根节点入栈，出栈的同时，先将右子树入栈，再将左子树入栈，循环执行即可

import java.util.*;

public class Solution {

    public int[] preorderTraversal (TreeNode root) {
        //根节点为空时，直接返回空数组
        if(root==null)return new int[0];
        //创建一个栈，初始状态将根节点入栈
        //创建一个List，存储出栈的节点的值
        Stack<TreeNode> st=new Stack<>();
        st.push(root);
        List<Integer> list=new ArrayList<>();
        TreeNode t;
        
        //当栈不为空时，循环
        //判断栈不为空，使用方法empty()
        while(!st.empty()){
            t=st.pop();
            list.add(t.val);
            if(t.right!=null){
                st.push(t.right);
            }
            if(t.left!=null){
                st.push(t.left);
            }
        }
        
        int[] res=new int[list.size()];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        
        return res;
    }
}