This is a fundamental and yet classic problem. I share my three solutions here:
- Iterative solution using stack ---
O(n)
time andO(n)
space; - Recursive solution ---
O(n)
time andO(n)
space (considering the costs of call stack); - Morris traversal ---
O(n)
time andO(1)
space!!!
Iterative solution using stack:
1 class Solution { 2 public: 3 vector<int> inorderTraversal(TreeNode* root) { 4 vector<int> nodes; 5 TreeNode* curNode = root; 6 stack<TreeNode*> toVisit; 7 while (curNode || !toVisit.empty()) { 8 if (curNode) { 9 toVisit.push(curNode); 10 curNode = curNode -> left; 11 } 12 else { 13 curNode = toVisit.top(); 14 toVisit.pop(); 15 nodes.push_back(curNode -> val); 16 curNode = curNode -> right; 17 } 18 } 19 return nodes; 20 } 21 };
Recursive solution:
1 class Solution { 2 public: 3 void inorder(TreeNode* node, vector<int>& nodes) { 4 if (!node) return; 5 inorder(node -> left, nodes); 6 nodes.push_back(node -> val); 7 inorder(node -> right, nodes); 8 } 9 vector<int> inorderTraversal(TreeNode* root) { 10 vector<int> nodes; 11 inorder(root, nodes); 12 return nodes; 13 } 14 };
Morris traversal:
1 class Solution { 2 public: 3 vector<int> inorderTraversal(TreeNode* root) { 4 vector<int> nodes; 5 TreeNode* curNode = root; 6 while (curNode) { 7 if (curNode -> left) { 8 TreeNode* predecessor = curNode -> left; 9 while (predecessor -> right && predecessor -> right != curNode) 10 predecessor = predecessor -> right; 11 if (predecessor -> right == NULL) { 12 predecessor -> right = curNode; 13 curNode = curNode -> left; 14 } 15 else { 16 predecessor -> right = NULL; 17 nodes.push_back(curNode -> val); 18 curNode = curNode -> right; 19 } 20 } 21 else { 22 nodes.push_back(curNode -> val); 23 curNode = curNode -> right; 24 } 25 } 26 return nodes; 27 } 28 };