题目

• 概述：给定一个二叉树，返回它的前序遍历

  要求：使用非递归算法

• 输入：二叉树的根节点

• 输出：前序遍历值列表

• 出处：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

思路

• 前序遍历的顺序是根->左子树->右子树
• 由于访问完左子树后要访问右子树，所以要先把右子树的信息暂存，所以考虑用栈实现
• 根节点入栈
• 重复将栈顶元素出栈直至栈为空

1. 栈顶元素有右孩子，将右孩子入栈
2. 栈顶元素有左孩子，将左孩子入栈

代码

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode top;
        stack.push(root);
        while (!stack.isEmpty()) {
            top = stack.pop();
            result.add(top.val);
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
        return result;
    }
}