94. Binary Tree Inorder Traversal

發表於 | 分類於

problem

solution

option 1 - dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& ret){
        if(!root) return;
        inorder(root->left, ret);
        ret.push_back(root->val);
        inorder(root->right, ret);
        
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(root, ret);
        return ret;
    }
};

option 2 - iterative + stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> sta;
        TreeNode *p = root;
        vector<int> ret;
        while (p || !sta.empty()) {
            while (p) { // L
                sta.push(p);
                p=p->left; 
            }
            p = sta.top();
            sta.pop();
            ret.push_back(p->val);  // V
            p = p->right;   // R
            
            
        }
        return ret;
    }
};