(Leet Code c++)Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal

 

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

 

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

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

Example 4:

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

Example 5:

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

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

이진트리의 중위순회를 구현.

중위순회는 왼쪽 자식, 현재 노드, 오른쪽 자식 순서로 방문한다.

 

inorder 함수를 통해 현재 노드의 왼쪽 자식을 검사, 현재 노드의 value를 answer에 저장, 오른쪽 자식을 검사하여 중위순회를 구현할 수 있다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode * node, vector<int> &answer){
        if(node->left != NULL){
            inorder(node->left, answer);
        }
        
        answer.push_back(node->val);
        
        if(node->right != NULL){
            inorder(node->right, answer);
        }
    }
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> answer;
        
        if(root != NULL){
            inorder(root, answer);  
        }
        
        return answer;
    }
};