leetcode | 二叉树的前序遍历、中序遍历、后续遍历的非递归实现

Binary Tree Preorder Traversal：https://leetcode.com/problems/binary-tree-preorder-traversal/
Binary Tree Inorder Traversal ：https://leetcode.com/problems/binary-tree-inorder-traversal/
Binary Tree Postorder Traversal：https://leetcode.com/problems/binary-tree-postorder-traversal/

• 前序遍历：先访问该节点，然后访问该节点的左子树和右子树；
• 中序遍历：先访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
• 后序遍历：想访问该节点的左子树和右子树，然后访问该节点。

递归遍历

对于递归遍历比较简单：

void preorder(TreeNode* root) {
    if (root == NULL)
        return;
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root) {
    if (root == NULL)
        return;
    inorder(root->left);
    visit(root);
    inorder(root-<right);
}

void postorder(TreeNode* root) {
    if (root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

非递归（迭代）遍历

非递归实现在遍历根节点后还要回来，因此要基于栈（先进后出）来保存节点。

前序遍历

压入顺序：右子树->左子树->根节点
使得访问的时候的顺序成为：根->左子树->右子树

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

中序遍历

压入顺序：右子树->根->左子树
只有当左子树已经访问完后，才能访问根节点

对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        if (root == NULL)
            return result;
        TreeNode* p = root;
        while (!s.empty() || p != NULL) {
            if (p != NULL) {
                // push 左子树入栈
                s.push(p);
                p = p->left;
            } else {
                // 左子树为空时，访问该节点，然后访问右子树
                p = s.top();
                result.push_back(p->val);
                s.pop();
                p = p->right;
            }
        }
        return result;  
    }

后序遍历

先压入根，然后是右子树，最后左子树
要求最后访问根节点，即访问该根节点时必须访问完左子树和右子树，我们只需要保证访问某一节点时，该节点的右子树已经被访问，否则需要将该节点重新压入栈。

对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。

  vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL)
            return result;
        stack<TreeNode*> s;
        TreeNode* p = root;  //当前正访问的节点
        TreeNode* q;  //记录刚刚访问过的节点
        do{
            while (p != NULL) {
                s.push(p);
                p = p->left;
            }
            q = NULL;
            while (!s.empty()) {
                p = s.top();
                s.pop();
                if (p->right == q) {  //当右子树已经访问过了，才可以访问根
                    result.push_back(p->val);
                    q = p;  //记录刚刚访问过的节点
                } else {
                    s.push(p); //第一次访问到该节点，需要将它重新入栈
                    p = p->right;
                    break;
                }

            }
        } while (!s.empty());
        return result;
    }

参考资料
二叉树的非递归遍历 http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html