145.二叉树的后序遍历  145. 二叉树的后序遍历 - 力扣（LeetCode）

 

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> vec;
        if(root == NULL) return vec;
        TreeNode* guard = root;//一开始，让哨兵站在根节点
        st.push(guard);
        while(!st.empty()) {
            TreeNode* cur = st.top();
            // 有左树且左树没处理过（左孩子存在且左右无哨兵）
            if(cur->left && cur->left != guard && cur->right != guard) {
                st.push(cur->left);
            }
            // 有右树且右树没有处理过（右孩子存在且右无哨兵）
            else if(cur->right && cur->right != guard) {
                st.push(cur->right);
            }
            // 左树、右树 没有 或者 都处理过了
            else{
                guard = st.top();
                vec.push_back(guard->val);
                st.pop();
            }
        }
        return vec;
    }
};