二叉树非递归遍历

（一）先序遍历

解法一：

vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> vec;
        if(!root) return vec;
        st.push(root);
        while(!st.empty()){
            TreeNode* tmp = st.top();
            st.pop();
            vec.push_back(tmp -> val);
            if(tmp -> right) st.push(tmp -> right);
            if(tmp -> left) st.push(tmp -> left);
        }
        return vec;
}

解法二（较通用的辅助结点法）：

vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> vec;
        TreeNode* p = root;
        while(!st.empty() || p){
            if(p){
                st.push(p);
                vec.push_back(p -> val);
                p = p -> left;
            }
            else{
                p = st.top() -> right;
                st.pop();
            }
        }
        return vec;
}

解法三（调整结点指向的无额外空间解法）：

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vec;
        if(!root) return vec;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur){
            if(cur -> right == NULL){
                vec.push_back(cur -> val);
                cur = cur -> left;
            }
            else{
                if(cur -> left == NULL){
                    cur -> left = cur -> right;
                    cur -> right = NULL;
                }
                else{
                    pre = cur -> left;
                    while(pre -> right)
                        pre = pre -> right;
                    pre -> right = cur -> right;
                    cur -> right = NULL;
                }
            }
        }
        return vec;
}

（二）中序遍历

解法一（较通用的辅助结点法）：

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* p = root;
        while(!st.empty() || p){
            if(p){
                st.push(p);
                p = p -> left;
            }
            else{
                p = st.top();
                st.pop();
                res.push_back(p -> val);
                p = p -> right;
            }
        }
        return res;
}

解法二（调整结点指向的无额外空间解法）：

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur){
            if(cur -> left == NULL){
                res.push_back(cur -> val);
                cur = cur -> right;
            }
            else{
                //find the rightmost
                pre = cur -> left;
                while(pre -> right)
                    pre = pre -> right;
                pre -> right = cur;
                TreeNode* tmp = cur -> left;
                cur -> left = NULL;
                cur = tmp;
            }
        }
        return res;
}

（三）后序遍历

要点：要加入一个结点访问次数的标志

解法一（辅助结点）：

vector<int> postorderTraversal(TreeNode* root) {
        map<TreeNode*, int> mp;
        vector<int> vec;
        stack<TreeNode*> st;
        TreeNode* p = root;
        while(!st.empty() || p){
            if(p){
                st.push(p);
                mp[p] = 0;
                p = p -> left;
            }
            else{
                p = st.top();
                mp[p]++;
                if(mp[p] == 1)
                    p = p -> right;
                else{   //mp[p] == 2
                    vec.push_back(p -> val);
                    st.pop();
                    p = NULL;
                }
            }
        }
        return vec;
}

（当结点左边访问完之后mp=1， 结点右边访问完之后mp=2）

解法二（JAVA）：
设置一个PowerNode类记录是否访问过左右子树

public List<Integer> postorderTraversal(TreeNode root) {
        Stack<PowerNode> s = new Stack<PowerNode>();
        List<Integer> res = new LinkedList<Integer>();
        if(root!=null) s.push(new PowerNode(root, false));
        while(!s.isEmpty()){
            PowerNode curr = s.peek();
            //如果是第二次访问，就计算并pop该节点
            if(curr.visited){
                res.add(curr.node.val);
                s.pop();
            } else {
            //如果是第一次访问，就将它的左右节点加入stack，并设置其已经访问了一次
                if(curr.node.right!=null) s.push(new PowerNode(curr.node.right, false));
                if(curr.node.left!=null) s.push(new PowerNode(curr.node.left, false));
                curr.visited = true;
            }
        }
        return res;
    }
    
    private class PowerNode {
        TreeNode node;
        boolean visited;
        public PowerNode(TreeNode n, boolean v){
            this.node = n;
            this.visited = v;
        }
    }

解法三（反向插入）：
每次加到头部，这样根节点自然就到了尾部，符合“左右根”的次序。

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}