LeetCode_2/94-Binary-Tree-Inorder-Traversal.cpp at main · argon2r/LeetCode_2 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//-------------------Method-1 : RECURSIVE------------------------
// class Solution {
// public:
//     void inOrder(TreeNode* root , vector<int> &ans){
//         if(root == NULL) return;
//         inOrder(root->left , ans);
//         ans.push_back(root->val);
//         inOrder(root->right , ans);
//     }

//     vector<int> inorderTraversal(TreeNode* root) {
//         vector<int> ans;
//         inOrder(root , ans);
//         return ans;
//     }
// };

//-----------Metod-2 : ITERATIVE------------------
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* node = root;

        while(st.size()>0 || node){
            if(node){
                st.push(node);
                node = node->left;
            }
            else{
                TreeNode* temp = st.top();
                st.pop();
                ans.push_back(temp->val);
                node = temp->right;
            }
        }
        return ans;
    }
};