1+ /*
2+ * Problem: 94
3+ * Name: Binary Tree Inorder Traversal
4+ * Difficulty: Medium
5+ * Topic: Binary Trees
6+ * Link: https://leetcode.com/problems/binary-tree-inorder-traversal
7+ */
8+
9+ #include < bits/stdc++.h>
10+ #include < cstddef>
11+ #include < vector>
12+ using namespace std ;
13+
14+ struct TreeNode {
15+ int val;
16+ TreeNode *left;
17+ TreeNode *right;
18+ TreeNode () : val(0 ), left(nullptr ), right(nullptr ) {}
19+ TreeNode (int x) : val(x), left(nullptr ), right(nullptr ) {}
20+ TreeNode (int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
21+ };
22+
23+ // Stack
24+ // Time Complexity: O(n)
25+ // Space Complexity: O(n)
26+ vector<int > inorderTraversal (TreeNode* root) {
27+ if (root == nullptr ) {return {};}
28+ vector<int > result;
29+ stack<TreeNode*> remaining;
30+ TreeNode* current = root;
31+
32+ while (!remaining.empty () || current != nullptr ) {
33+ while (current != nullptr ) {
34+ remaining.push (current);
35+ current = current->left ;
36+ }
37+ current = remaining.top ();
38+ remaining.pop ();
39+ result.push_back (current->val );
40+ current = current->right ;
41+ }
42+ return result;
43+ }
44+
45+ // Call Stack
46+ // Time Complexity: O(n)
47+ // Space Complexity: O(n)
48+ void inorderHelper (TreeNode* node, vector<int >& result);
49+ vector<int > inorderTraversal (TreeNode* root) {
50+ vector<int > result;
51+ inorderHelper (root, result);
52+ return result;
53+ }
54+ void inorderHelper (TreeNode* node, vector<int >& result){
55+ if (node == nullptr ) {return ;}
56+ inorderHelper (node->left , result);
57+ result.push_back (node->val ),
58+ inorderHelper (node->right , result);
59+ }
60+
61+ // Morris Traversal
62+ // Time Complexity: O(n)
63+ // Space Complexity: O(1)
64+ vector<int > inorderTraversal (TreeNode* root) {
65+ vector<int > nodes;
66+ while (root != nullptr ) {
67+ if (root -> left != nullptr ) {
68+ TreeNode* pre = root -> left;
69+ while (pre->right != nullptr && pre->right != root) {
70+ pre = pre -> right;
71+ }
72+ if (pre -> right == nullptr ) {
73+ pre -> right = root;
74+ root = root -> left;
75+ } else {
76+ pre -> right = NULL ;
77+ nodes.push_back (root -> val);
78+ root = root -> right;
79+ }
80+ } else {
81+ nodes.push_back (root -> val);
82+ root = root -> right;
83+ }
84+ }
85+ return nodes;
86+ }
0 commit comments