[LeetCode] 94. Binary Tree Inorder Traversal c++

• 문제

Given the root of a binary tree, return the inorder traversal of its nodes' values.

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

트리 순회 알고리즘 중 중위 순회(Inorder Traversal) 를 사용하여 방문한 순서대로 노드 값을 출력하는 문제이다.

 

 

Inorder Traversal(중위 순회) 란? (<- 클릭)

중위 순회는 부모의 왼쪽 자식 노드  → 부모 노드  → 부모의 오른쪽 자식 노드  순으로 방문하는 트리 순회 알고리즘입니다.

 

Left child node -> Parents node -> Right child node

 

위의 트리를 중위 순회를 하면 {1, 2, 3, 4, 5, 6, 7, 8} 순으로 방문하게 됩니다.

 

• 문제 해결

void visitInorder(TreeNode* root, vector<int>& v) {
    if (!root) {
        return;
    }
    else {
        visitInorder(root->left, v);
        v.push_back(root->val);
        visitInorder(root->right, v);
    }
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> v;
    visitInorder(root, v);

    return v;
}

다른 방법

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root){ 
        if(root==NULL)
           return {};
        vector<int> vec;
        stack<TreeNode*> s;
        while(true){
            if(root!=NULL){
               s.push(root);
               root=root->left; 
            }
            else{
                if(s.empty())
                    break;
                root=s.top();
                s.pop();
                vec.push_back(root->val);
                root=root->right;
            }
        }
        return vec;
    }
};