Algorithm - binary tree traversal

1. 基本概念:

• rooted binary tree: has 1 root, every node has {0-2} children
• full/poper/plane binary tree: binary tree, every node has {0,2} children
• perfect/complete binary tree: binary tree, all interior nodes has {2} children ,all leaves have same depth.

2. 递归遍历

Code speaks:

protected void traversalRecursion(Node2 root, String method) {
    if (null == root) {
        return;
    }

    switch (method) {
        case "pre-order":
            visit(root);
            traversalRecursion(root.left, method);
            traversalRecursion(root.right, method);
            break;
        case "in-order":
            traversalRecursion(root.left, method);
            visit(root);
            traversalRecursion(root.right, method);
            break;
        case "post-order":
            traversalRecursion(root.left, method);
            traversalRecursion(root.right, method);
            visit(root);
            break;
        default:
            throw new IllegalArgumentException("unknown traversalRecursion method: " + method);
    }
}

3. 迭代遍历

3.1 Pre Order Traversal: N-L-R

需要使用两个变量：current和stack

• 先访问current的值，然后把current压栈，留着后面访问right用
• 游标移到current.left, 继续
• 如果current为null，但是stack不空，那么出栈，游标移到pop.right

主要思路：先一直向左冲到底，并一路压栈，见底后拿出栈顶，冲向栈顶右边，继续一直向左冲到底。
结束条件：撞见底，栈为空。
所以：需要一个冲的当前位置，需要一个栈。

protected void preOrderTraversalIteration() {
    Stack<Node2> st = new Stack<Node2>();
    Node2 current = this;
    while (true) {
        if (null != current) { //going down
            visit(current);
            st.push(current);
            current = current.left;
        } else if (!st.isEmpty()) {//visiting stack
            current = st.pop().right; //visit stack head
        } else {
            break;
        }
    }
}

3.2 In Order Traversal: L-N-R

与NLR类似

protected void inOrderTraversalIteration() {
    Stack<Node2> st = new Stack<Node2>();
    Node2 current = this;
    while (true) {
        if (null != current) { //going down
            st.push(current);
            current = current.left;
        } else if (!st.isEmpty()) {//visiting stack
            Node2 popHead = st.pop();
            visit(popHead);
            current = popHead.right;
        } else {
            break;
        }
    }
}

3.3 Post Order Traversal: L-R-N

复杂点，思路为：
一路向左冲到底，并一路压栈，
见底后冲进栈顶，如果栈顶的right是上次访问过的item，则visit栈顶然后出栈，否则冲向栈顶右边。

protected void postOrderTraversalIteration() {
    Deque<Node2> st = new LinkedList<Node2>();
    Node2 current = this;
    Node2 lastVisit = null;
    while (true) {
        if (null != current) { //going left
            st.addLast(current);
            current = current.left;
        } else if (!st.isEmpty()) {//visiting stack
            Node2 peekHead = st.getLast();
            if (lastVisit == peekHead.right) {
                visit(peekHead);
                lastVisit = st.removeLast();
            } else {
                current = peekHead.right;
                lastVisit = null; // going right
            }
        } else {
            break;
        }
    }
}

3.4 Level Order Traversal

protected void levelOrderTraversalIteration() {
    Queue<Node2> q = new LinkedList<Node2>();
    q.add(this);
    while (!q.isEmpty()) {
        Node2 current = q.remove();
        visit(current);
        if (null != current.left) {
            q.add(current.left);
        }
        if (null != current.right) {
            q.add(current.right);
        }
    }
}