[leetcode 94] Binary Tree Inorder Traversal

Example 1:

Input: root = [1,null,2,3] Output: [1,3,2]

 

Example 2:

Input: root = [] Output: []

 

Example 3:

Input: root = [1] Output: [1]

 

1) recursive 풀이

class Solution {
public:
    
    void Recursive(TreeNode* root, vector<int> &answer){
        
        if(root == nullptr){
            return;
        }
        
        Recursive(root->left, answer);
        answer.push_back(root->val);
        Recursive(root->right, answer);
        
    }
    vector<int> inorderTraversal(TreeNode* root) {
     
        vector<int> answer;
        //recursive
        Recursive(root, answer);
        
        return answer;
    }
};

 

2) stack 이용

using namespace std;
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> answer;
        
        //using stack
        stack<TreeNode *> s;
        TreeNode * cur = root;
        while(cur != nullptr || !(s.empty())){
            while(cur != nullptr){
                s.push(cur);
                cur = cur -> left;
            }
            cur = s.top();
            s.pop();
            answer.push_back(cur->val);
            cur = cur->right;
        }
        return answer;
    }
};

 

3) Morris

class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
     
        vector<int> answer;
        
       //moris traversal
        TreeNode *cur = root;
        while(cur!=nullptr){
            if(cur->left == nullptr){
                answer.push_back(cur->val);
                cur = cur->right;
            }else {
                TreeNode * sub = cur -> left;
                while(sub-> right!=nullptr){
                    sub = sub->right;
                }
                sub->right = cur;
                TreeNode * tmp = cur;
                cur = cur->left;
                tmp->left = nullptr;
            }
        }
        return answer;
    }
};