LeetCode-257 두 갈래 나무의 모든 경로

1535 단어

1. 제목 설명


두 갈래 나무를 정해서 뿌리 노드에서 잎 노드까지의 모든 경로를 되돌려줍니다.설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.예: 입력: 1/\2 3\5 출력: ["1->2->5", "1->3"]
설명: 모든 뿌리 노드에서 잎 노드까지의 경로: 1->2->5, 1->3

2. 문제 풀이 사고방식


두 갈래 나무를 두루 돌아다닐 때, 현재의 노드와 아이의 노드를 고려해야 한다.만약 현재의 노드가 잎 노드가 아니라면, 현재의 경로 끝에 이 노드를 추가하고, 이 노드를 두루 돌아다니는 모든 아이 노드로 귀속됩니다.만약 현재의 노드가 잎 노드라면, 현재의 경로 끝에 이 노드를 추가한 후, 뿌리 노드에서 잎 노드로 가는 경로를 얻을 수 있으며, 이 경로를 답안에 넣을 수 있다.

3. 코드 구현

#include
#include

using namespace std;
class Solution {
public:
    void constructPath(TreeNode* root, string path, vector& paths) {
        if (root != nullptr) {
            path.append(std::to_string(root->val));
            //  
            if ((root->left == nullptr) && (root->right == nullptr)) {
                paths.push_back(path); //  
            } else { //  
                path.append("->");
                constructPath(root->left, path, paths);
                constructPath(root->right, path, paths);
            }
        }
    }
    vector binaryTreePaths(TreeNode* root) {
        vector paths;
        string path = "";
        
        constructPath(root, path, paths);
        return paths;
    }
};

4. 총결산


en...나무 제목 재밌는데...많이 닦고 많이 닦고...참조 링크:https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode/
면접 문제 32.2: 두 갈래 나무를 여러 줄로 인쇄
671. 두 갈래 나무 중 두 번째로 작은 노드

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage