검지offer 시리즈-24.두 갈래 트리 중 하나가 되는 경로

1708 단어
Q: 두 갈래 나무의 노드와 정수를 입력하고 두 갈래 나무의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.(주의: 되돌아오는 값의list에서 수조의 길이가 큰 수조가 앞쪽으로) T: 주요 논리는 DFS 함수를 통해 귀속된다. 만약에 나의 루트 노드가 잎 노드가 아니라면expectNumber-root->val로 루트라는 층으로 아래의 모든 층의 기대치이다. 잎 노드로 귀속될 때까지 expcetNumber는 이 잎 노드의 모든 조상 노드의 값을 줄였다.그러면 이 잎 노드의val가 남은 기대치와 같으면 제목에 맞는 경로입니다.여기의vector &path는 인용을 사용합니다. 아래로 돌아가는 과정에서 이root->val 값을 빼면 팝이 이val을 떨어뜨립니다.귀환할 때, 문제의 경로에 부합되는 조상 노드에 대해 말하자면, 그것들의 뜻에 부합되는 path는allPath 수조에서, 그것의 path는 그것에서 잎 노드로 시작된다.만약 이 조상 노드가 뿌리 노드라면 뿌리 노드에서 잎 노드까지의 제목에 부합되는 경로도 allPath에 있다.제목에는 두 가지 점이 있다. 하나는 루트로 가는 경로이다.둘째, 제목에서 언급한 바와 같이, 되돌아오는 값의list에서 그룹의 길이가 큰 그룹이 앞에 있으며,sort로 정렬해야 한다.P.S. 사실 저는 allPath와 path를class에서 function 밖으로 쓰는 것이 좋다고 생각합니다.
    vector > FindPath(TreeNode *root, int expectNumber) {
        vector > allPath;
        vector path;
        if (root)
            DFS(root, expectNumber, allPath, path);
        stable_sort(allPath.begin(), allPath.end(), [](const vector& a, const vector& b) { return a.size() > b.size();});
        return allPath;
    }

    static void DFS(TreeNode *root, int sum, vector > &allPath, vector &path) {
        path.push_back(root->val);
        if(!root->left&&!root->right) {
            if (root->val == sum)
                allPath.push_back(path);
        }
        if (root->left)
            DFS(root->left, sum - root->val, allPath, path);
        if (root->right)
            DFS(root->right, sum - root->val, allPath, path);
        path.pop_back();
    }
첫 번째 배달은 자동화된 것이다
빠른 정렬 시간 복잡도와 공간 복잡도

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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