题解 | #二叉树的前序遍历# 非递归实现

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 {
    /**
     * 思路：利用栈的特点，从跟节点开始，先遍历左子树，将遍历的节点压入栈，
	 *      当没有遍历到左孩子的时候就可以通过弹出节点来找到右孩子，当节点不为null时又可以继续遍历
	 * 		其实就是一个有去有回这样的一个动作
     *		需要同时满足栈为空且遍历完所有节点时结束循环
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            if(curr != null){
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }else{
                TreeNode pop = stack.pop();
                curr = pop.right;
            }
           
        }
        return list.stream().mapToInt(Integer::intValue).toArray();;
    }
    
}