In Order Travesal with Stack

出处

Given a binary tree, implement the In-Order Traversal using a stack

Solution

中序遍历(In-Order Traversal)的规则是：1) 先遍历左子树 2) 访问当前节点 3) 遍历右子树。我们先逻辑上重现整个遍历过程，对于某个上层节点，先向左下降到下一层，解决子问题，回到当前节点，向右下降到下一层。很显然，遍历子树的过程是一个自上而下结构：从顶层出发，逐渐向下扩散。实际计算时，我们先解决子问题(遍历左子树)，再利用子问题的结果解决当前问题(访问当前节点，转向右子树)。如果用栈作为辅助结构消除递归，由于子问题是遍历左子树，所以我们将左孩子以自上而下的顺序放入栈，每次弹出时，都意味着子问题已经解决好了，需要解决当前问题，即访问当前节点，再转向右子树。

Complexity

该算法不重复地扫描所有节点，故时间复杂度O(n)。

Code

void inordertraversal(Node root){
    if (root == null) return;
    Stack<Node> stack = new Stack<Node>();
    while( !stack.isEmpty() || root != null){
        if (root != null){
            stack.push(root);
            root = root.left;
        } else {
            Node cur = stack.top();
            stack.pop();
            visit(cur);
            root = root.right;
        }
    }
}