257. Binary Tree Paths

https://leetcode.com/problems/binary-tree-paths/

Binary Tree Paths - LeetCode

 

이진트리의 root가 주어졌을 때, root부터 leaf 까지의 모든 경로를 string vector에 담아 리턴하는 문제다.

문자열로 반환해야 해서 int 타입의 val을 string으로 변환하는 to_string 함수를 사용한다.

양쪽의 자식노드가 모두 없으면 지금까지 경로를 벡터에 담아 종료한다.

(인자를 레퍼런스로 주지 않는 이유는 양쪽으로 갈라져야 하는데 양쪽에서 수정되면 곤란하기 때문에 pass by value)

 

/**
 * 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 solve(TreeNode* node, string str) {       
        if (!node->left && !node->right) {
            v_.push_back(str);
            return;
        }
        
        if (node->left) {
            solve(node->left, str + "->" + to_string(node->left->val));
        }
        
        if (node->right) {
            solve(node->right, str + "->" + to_string(node->right->val));
        }
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        if (!root) {
            return v_;
        }

        solve(root, to_string(root->val));
        return v_;
    }
private:
    vector<string> v_;
};