94 Binary Tree Inorder Traversal
Description
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
My Solution
-
recursive
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution{ public: vector<int> inorderTraversal(TreeNode* root){ vector<int> ans; inorder(root, ans); return ans; } void inorder(TreeNode* root, vector<int> &ans){ if (root){ inorder(root->left, ans); ans.push_back(root->val); inorder(root->right, ans); } } }
-
iterative
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ans; inorder(root, ans); return ans; } void inorder(TreeNode* root, vector<int> &ans){ if (!root){ return; } stack<TreeNode*> s; while(!s.empty() || root){ if (root){ s.push(root); root = root->left; }else{ root = s.top(); ans.push_back(root->val); s.pop(); root = root->right; } } }
