面接でよく見られるアルゴリズムのツリーの後続ループ(逆出力前シーケンスループのミラーバージョン)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        if (root == NULL)
            return {};
        
        //       ：  -   -  
        //             ：  -   -  
        //            
        //        

        //            
        vector visit;
        TreeNode *point = root;
        vector nodes;

        while (!nodes.empty() || point != NULL) {
            //   point
            visit.push_back(point->val);
            //   point     ，     ，  point  nodes ，              
            //         
            if (point->left != NULL && point->right != NULL) {
                nodes.push_back(point);
                point = point->right;
            }
            // point   /   ，   point   /   
            else if (point->right != NULL)
                point = point->right;
            else if (point->left != NULL)
                point = point->left;
            else{
                // point    
                //   nodes  ，    
                //   point  nodes          
                //    nodes        
                if (nodes.empty())
                    break;
                point = nodes.back()->left;
                nodes.pop_back();
            }
        }

        //         
        reverse(visit.begin(), visit.end());
        return visit;
    }
};