Leetcode:Populating Next Right Pointers in Each Node 두 갈래 트리 채우기 next 포인터

Populating Next Right Pointers in Each Node :
populating-next-right-pointers-in-each-node-ii :
Given a binary tree

struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL .
Initially, all next pointers are set to NULL .

문제 풀이 분석:
1번 문제는 2번 문제의 특례입니다. 2번 코드는 아무런 변경도 하지 않고 accepted 1번 문제를 받아들일 수 있습니다.
그러나 첫 번째 문제는 O(1) 공간이 필요하고 두 갈래 나무로 귀속시키면 된다

먼저 두 번째 문제를 완성하려면 두 갈래 나무의 각 층의 결점의next바늘을 채워야 한다. 여기에 층계의 개념이 하나 있는데 두 갈래 나무의 층계가 두루 돌아다니는 것을 먼저 생각해야 한다.
모든 층에 대해 우리는 모든 결점의next를 서열의 후계 결점을 가리키고, 모든 층의 마지막 결점의next 바늘을 NULL로 설정하면 된다는 것을 쉽게 생각할 수 있다.
두 갈래 나무의 층계가 두루 다니면 아주 능숙하게 쓸 수 있을 것이다

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
        vector<vector<TreeLinkNode*>> result;
        levelOrder(root, 1, result);
        for (int i = 0; i < result.size(); ++i) {
            for (int j = 0; j < result.at(i).size(); ++j) {
                if (j != result.at(i).size() - 1) {
                    result.at(i).at(j)->next = result.at(i).at(j+1);
                } else {
                    result.at(i).at(j)->next = NULL;
                }
            }
        }
    }
    
    void levelOrder(TreeLinkNode* root, int level, vector<vector<TreeLinkNode*>>& result) {
        if (root == NULL) return;
        if (level > result.size()) {
            result.push_back(vector<TreeLinkNode*>());
        }
        result.at(level-1).push_back(root);
        levelOrder(root->left, level + 1, result);
        levelOrder(root->right, level + 1, result);
    }
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Leetcode:Populating Next Right Pointers in Each Node 두 갈래 트리 채우기 next 포인터

좋은 웹페이지 즐겨찾기