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

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

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

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

    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }

    return result;
}

算法流程:

1. 定义result存储结果,stack用于中序遍历,curr指向当前节点。
2. curr不是null且没有左子节点,一直左移。
3. 如果curr为空,stack非空,出栈curr访问,curr右移。
4. 重复步骤2和3,直到curr和stack均为空,返回result。
5. 特殊情况,root为空,返回result。

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

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

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