前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
前序遍历：root、root->left、root->right
非递归实现需要一个辅助栈

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
            vector<int> ret;
            if (root == nullptr) {
                return ret;
            }
            stack<TreeNode*> stk;
            stk.push(root);
            while (!stk.empty()) {
                TreeNode* cur = stk.top();
                stk.pop();
                ret.push_back(cur->val);
                if (cur->right) {
                    stk.push(cur->right);
                }
                if (cur->left) {
                    stk.push(cur->left);
                }
            }
            return ret;
    }
};

中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
中序遍历：root->left、root、root->right
非递归实现需要一个辅助栈

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) {
            return ret;
        }
        stack<TreeNode*> stk;
        TreeNode* mov = root;
        while (mov != nullptr || !stk.empty()) {
            while (mov != nullptr) {
                stk.push(mov);
                mov = mov->left;
            }
            if (!stk.empty()) {
                TreeNode* cur = stk.top();
                stk.pop();
                ret.push_back(cur->val);
                mov = cur->right;
            }
        }
        return ret;
    }

后序遍历

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
后序遍历：root->left、root->right、root
非递归实现需要一个辅助栈
具体过程：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> ret;
        if (root == NULL) {
            return ret;
        }
        TreeNode* pre = NULL;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            if ((cur->left == NULL && cur->right == NULL) || (pre != NULL && (pre == cur->left || pre == cur->right))) {
                ret.push_back(cur->val);
                pre = cur;
                stk.pop();
            } else {
                if (cur->right) {
                    stk.push(cur->right);
                }
                if (cur->left) {
                    stk.push(cur->left);
                }
            }
        }
        return ret;
    }
};