[LeetCode] Binary Tree Inorder Traversal

Binary Tree Inorder Traversal - LeetCode

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

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

 

/**
 * 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> answer;
        traverse(root, answer);
        return answer;
    }
    
private:
    void traverse(TreeNode* root, vector<int> &answer) {
        if (root != NULL) {
            traverse(root->left, answer);
            answer.push_back(root->val);
            traverse(root->right, answer);
        }
    }
};

흔히 볼 수 있는 트리 순회 문제입니다. inorder의 경우 중위 순회로 왼쪽 - 중간 - 오른쪽 순서대로 순회를 하게 되고 이를 재귀적으로 풀이하면 위와 같이 풀이할 수 있습니다.

먼저 root node가 NULL이 아니라면, 왼쪽 노드를 시작으로 순회를 하고, answer에 root의 value를 추가, 오른쪽 노드를 순회하는 방식으로 트리를 탐색합니다. 이렇게 되면 왼쪽 노드를 시작으로 만들어진 트리 노드들이 다 추가 된 후 루트 노드가 추가되고, 오른쪽 노드를 시작으로 만들어진 노드들이 추가됩니다.