数的结构

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

前序构建二叉树序列

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    if(!root) return ans;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty())
    {
        TreeNode* node = s.top();// 先将压入栈中的结点取出
        ans.push_back(node->val);// 将结点放入ans中
        s.pop();// 弹出已经用过的节点    
        // 栈的特性：先进后出
        if (node->right)// 先压入右边节点
            s.push(node->right);
        if (node->left)// 再压入左边节点
            s.push(node->left);            
    }
    return ans;
}

中序构建二叉树序列

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (!s.empty() || node)
    {
        while (node)// 对当前节点一直遍历，直到找到最左子树的节点为止
        {
            s.push(node);
            node = node->left;
        }
        if (!s.empty())
        {
            node = s.top(); // 从最左子树的节点开始，以此取出和弹出
            ans.push_back(node->val);// 将结点放入ans中
            s.pop();
            node = node->right;// 根据左中右的原则，还需要将右子树压入
        }
    }
    return ans;
}

后序构建二叉树序列

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    if(!root) return ans;
    stack<TreeNode*> s;
    s.push(root);
    // 先进行反向操作，最后再reverse
    // 左右中
    while (!s.empty())
    {
        TreeNode* node = s.top();// 先将中节点压入
        ans.push_back(node->val);
        s.pop();            
        if (node->left)// 寻找左节点
            s.push(node->left);
        if (node->right)// 寻找右节点
            s.push(node->right);
        // 根据栈的特性，下次循环，先取右节点
    }
    reverse(ans.begin(), ans.end()); // 反向
    return ans;
}