题解 | #二叉树的前序遍历#

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) {
        // write code here
        // 使用 数组存储遍历的结果集
        List<Integer> list = new ArrayList<>();
        // 使用栈来存储节点
        Stack<TreeNode> stackNode = new Stack<>();
        stackNode.push(root);
        TreeNode temp;
        while (!stackNode.empty()) {
            temp = stackNode.pop();
            while (temp != null) {
                list.add(temp.val);
                if (temp.right != null) {
                    // 存在右孩子就先存储起来
                    stackNode.push(temp.right);
                }
                temp = temp.left; // 寻找左孩子
            }
        }
        int len = list.size();
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

非递归版本的先序遍历，使用 stack 存储后面要访问的节点，一次遍历即可。