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

January LeetCoding Challenge 9

Description

Binary Tree Preorder Traversal

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

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

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

Constraints:

• The number of 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> preorderTraversal(TreeNode* root) {
    vector<int> answer;
    TreeNode *cur = root;
    while(cur) {
      if(!(cur->left)) {
        answer.push_back(cur->val);
        cur = cur->right;
      } else {
        TreeNode *left = cur->left;
        while(left->right && left->right != cur) {
          left = left->right;
        }
        if(left->right == cur) {
          left->right = nullptr;
          cur = cur->right;
        } else {
          left->right = cur;
          answer.push_back(cur->val);
          cur = cur->left;
        }
      }
    }
    return answer;
  }
};

// Accepted
// 69/69 cases passed (6 ms)
// Your runtime beats 20.93 % of cpp submissions
// Your memory usage beats 44.83 % of cpp submissions (8.4 MB)