[LeetCode] Binary Tree Postorder Traversal-白红宇

This is a fundamental and yet classic problem. I share my three solutions here:

Iterative solution using stack --- O(n) time and O(n) space;

Recursive solution --- O(n) time and O(n) space (considering the costs of call stack);

Morris traversal --- O(n) time and O(1) space!!!

Iterative solution using stack:

1 vector
     
       postorderTraversal(TreeNode* root) { 2     vector
      
        nodes; 3     stack
       
         toVisit; 4     TreeNode* curNode = root; 5     TreeNode* lastNode = NULL; 6     while (curNode || !toVisit.empty()) { 7         if (curNode) { 8             toVisit.push(curNode); 9             curNode = curNode -> left;10         }11         else {12             TreeNode* topNode = toVisit.top();13             if (topNode -> right && lastNode != topNode -> right)14                 curNode = topNode -> right;15             else {16                 nodes.push_back(topNode -> val);17                 lastNode = topNode;18                 toVisit.pop();19             }20         }21     }22     return nodes;23 }

Recursive solution:

1 void postorder(TreeNode* root, vector
     
      & nodes) { 2     if (!root) return;  3     postorder(root -> left, nodes); 4     postorder(root -> right, nodes); 5     nodes.push_back(root -> val); 6 } 7 vector
      
        postorderTraversal(TreeNode* root) { 8     vector
       
         nodes; 9     postorder(root, nodes);10     return nodes;11 }

Morris traversal:

1 void reverseNodes(TreeNode* start, TreeNode* end) { 2     if (start == end) return; 3     TreeNode* x = start; 4     TreeNode* y = start -> right; 5     TreeNode* z; 6     while (x != end) { 7         z = y -> right; 8         y -> right = x; 9         x = y;10         y = z;11     }12 }13 void reverseAddNodes(TreeNode* start, TreeNode* end, vector
     
      & nodes) {14     reverseNodes(start, end);15     TreeNode* node = end;16     while (true) {17         nodes.push_back(node -> val);18         if (node == start) break;19         node = node -> right;20     }21     reverseNodes(end, start);22 }23 vector
      
        postorderTraversal(TreeNode* root) {24     vector
       
         nodes;25     TreeNode* dump = new TreeNode(0);26     dump -> left = root;27     TreeNode* curNode = dump;28     while (curNode) {29         if (curNode -> left) {30             TreeNode* predecessor = curNode -> left;31             while (predecessor -> right && predecessor -> right != curNode)32                 predecessor = predecessor -> right;33             if (!(predecessor -> right)) {34                 predecessor -> right = curNode;35                 curNode = curNode -> left;36             }37             else {38                 reverseAddNodes(curNode -> left, predecessor, nodes);39                 predecessor -> right = NULL;40                 curNode = curNode -> right;41             }42         }43         else curNode = curNode -> right;44     }45     return nodes;46 }