(Easy - Backtracking) Leetcode - 257. Binary Tree Paths

 

 

이 문제는 이진 트리가 주어지면 root부터 leaf  node, 즉 맨 밑의 정점까지 갈 수 있는 모든 경로를 출력하는 문제입니다.

 

경로를 출력해야 하므로 DFS를 사용하면 됩니다.

저는 Recursion DFS 방법을 사용했습니다.

 

/**
 * 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) {}
 * };
 */
    void DFS(vector<string>& ans, string path, TreeNode* node) {
        if (node == nullptr) 
            return;

        path += std::to_string(node->val);
		
        // leaf node에 도달했으면
        if (node->left == nullptr && node->right == nullptr) {
            ans.push_back(path); // 여태까지의 경로를 추가
            return;
        }
        
        // 자식 노드로 내려가기
        path += "->";
        if (node->left) 
            DFS(ans, path, node->left);
        if (node->right)
            DFS(ans, path, node->right);
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        DFS(ans, "", root);
        return ans;
    }
};

 

하지만 이 방법은 매번 DFS 함수가 불릴 때 string 클래스를 생성하고 다른 string을 이어주는(Concatenate)게 많습니다.

이렇게 매번 string을 생성하면 시간이 더 걸릴 수 있습니다.

 

그래서 조금 더 성능을 높이기 위해 경로의 Node의 값만을 순서대로 저장하는 vector를 따로 만들어 경로를 저장하기 위해 사용했습니다.

이 저장된 경로를 사용해 leaf node에 도달하면 string으로 만들어 정답을 저장하는 배열에 저장해 조금 더 빠르게 완료할 수 있습니다.

/**
 * 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) {}
 * };
 */
 	// 매번 string을 생성하기 보단 vector<int>로 경로를 따로 저장
    void DFSHelper(vector<string>& ans, vector<int>& path, TreeNode* node) {
        if (node == nullptr)
            return;
        
        path.push_back(node->val);

		// leaf node에 도달하면 저장된 경로를 string path로 만들기
        if (!node->left && !node->right) {
            string pathStr;
            for (int i = 0; i < path.size() - 1; i++)
                pathStr += std::to_string(path[i]) + "->";
            pathStr += std::to_string(path.back());

            ans.push_back(pathStr);
        }

        if (node->left)
            DFSHelper(ans, path, node->left);
        if (node->right)
            DFSHelper(ans, path, node->right);

        path.pop_back(); // 다른 경로를 가기 위해 맨 마지막으로 들린 node를 경로에서 빼주기
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        vector<int> path;
        DFSHelper(ans, path, root);
        return ans;
    }
};