binary-tree-traversal-iterative.cpp (1330B)
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10 * }; 11 */ 12 class Solution { 13 public: 14 vector<int> inorderTraversal(TreeNode* root) { 15 16 auto* start = root; 17 18 // left, current, right 19 auto order = vector<int>{}; 20 auto stack = vector<TreeNode*>{root}; 21 22 while(stack.size() > size_t(0)) { 23 auto current = stack.back(); 24 stack.pop_back(); 25 26 if(current == nullptr) { 27 continue; 28 } 29 30 if(current->left == nullptr && current->right == nullptr) { 31 order.push_back(current->val); 32 continue; 33 } 34 35 stack.push_back(current->right); 36 current->right = nullptr; 37 stack.push_back(current); 38 stack.push_back(current->left); 39 current->left = nullptr; 40 } 41 42 // reset to point at root at the end so 43 // no side effects for this specific function. 44 45 root = start; 46 return order; 47 } 48 };