Leetcode: 94. Binary Tree Inorder Traversal (Brute force)
Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector res;
helper(root, res);
return res;
}
void helper(TreeNode* root, vector& res)
{
if (root != nullptr)
{
helper(root->left, res);
res.push_back(root->val);
helper(root->right, res);
}
}
}
Example
Input:
1
\
2
/
3
Output: [1, 3, 2]
Complexity Analysis
The time complexity of the inorderTraversal
function is O(n), where n is the number of nodes in the binary tree. This is because we need to visit each node once to perform the inorder traversal.
The space complexity is O(n) as well, as we need to store the values of all the nodes in the output vector. In the worst case, the binary tree can be skewed, leading to a recursion depth of n.
Comments
Post a Comment