Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 25

Description

Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes' values.

 

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

class Solution {
public:
  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> answer;
    TreeNode *cur = root;
    while(cur) {
      if(!(cur->right)) {
        answer.push_back(cur->val);
        cur = cur->left;
      } else {
        TreeNode *right = cur->right;
        while(right->left && right->left != cur) {
          right = right->left;
        }
        if(right->left == cur) {
          right->left = nullptr;
          cur = cur->left;
        } else {
          answer.push_back(cur->val);
          right->left = cur;
          cur = cur->right;
        }
      }
    }
    reverse(answer.begin(), answer.end());
    return answer;
  }
};