如何实现二叉树的前序遍历非递归算法？

二叉树的前序遍历(Preorder Traversal)问题是先访问根节点,然后前序遍历左子树,最后前序遍历右子树。

我们可以使用栈实现二叉树的前序遍历非递归算法:

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        result.add(curr.val);
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }

    return result; 
}

算法流程:

1. 定义result存储结果,stack用于前序遍历。
2. 根节点入栈。
3. 当栈非空时循环。出栈当前节点curr,将值加入result。
4. 右子节点先入栈,左子节点后入栈。(右左中)
5. 重复步骤3和4,直到栈为空,返回result。
6. 特殊情况,root为空,返回result。

时间复杂度O(n),空间复杂度O(n)。

所以,二叉树前序遍历的关键是:

1. 使用栈模拟递归调用栈。
2. 出栈根节点,访问根节点,将右子节点和左子节点依次入栈。
3. 重复步骤2,直到栈为空,得到结果。
4. 与递归前序遍历相比,只是使用栈代替了递归调用栈。