94. Binary Tree Inorder Traversal
1. Description
Given the root of a binary tree, return the inorder traversal of its nodes' values.
2. Example
Example 1:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,2]
Output: [2,1]
Example 5:
Input: root = [1,null,2]
Output: [1,2]
3. Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
4. Follow Up
- Recursive solution is trivial, could you do it iteratively?
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in m_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// vector<int> inorderTraversal(TreeNode* root)
vector<int> inorderTraversal(TreeNode *m_root)
{
vector<int> result;
stack<TreeNode*> travelNodes;
auto root = m_root;
while(root != nullptr || !travelNodes.empty())
{
if(root == nullptr)
{
root = travelNodes.top();
root->left = nullptr;
travelNodes.pop();
}
if(root->left != nullptr)
{
travelNodes.push(root);
root = root->left;
}
else
{
result.push_back(root->val);
root = root->right;
}
}
return result;
}
};
5.1 Morris Traversal(Follow Up)
n is the number of nodes in m_root
Time complexity: O(n)
Space complexity: O(n)
// we have to say that the morris traversal will take constant memory, its space complexity results from result vector, or we can say this method has O(1) space complexity
class Solution
{
public:
// vector<int> inorderTraversal(TreeNode* root)
vector<int> inorderTraversal(TreeNode *m_root)
{
vector<int> result;
for(TreeNode *current = m_root, *previous = nullptr; current; )
{
if(current->left == nullptr)
{
result.push_back(current->val);
current = current->right;
}
else
{
previous = current->left;
while(previous->right && previous->right != current) previous = previous->right;
if(previous->right == nullptr)
{
previous->right = current;
current = current->left;
}
else
{
previous->right = nullptr;
result.push_back(current->val);
current = current->right;
}
}
}
return result;
}
};