두 갈래 트리 너비 우선 검색(계층 이동, BFS)

두 갈래 나무 구조:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

두 갈래 트리 너비 우선 검색:

두 갈래 나무의 층수에 따라 왼쪽에서 오른쪽으로 두 갈래 나무의 노드를 방문한다.예를 들어, 두 갈래 트리를 지정합니다.

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

너비에 따라 우선 검색: 1층 루트 노드: 5 2층 왼쪽부터 오른쪽: 4->8 3층 왼쪽부터 오른쪽: 11->13->4 4층 왼쪽부터 오른쪽: 7->2->5->1 마지막 출력: 5->4->8->11->13->4->7->2->5->1;ok, 다음은 이 문제를 어떻게 프로그래밍해야 하는지를 고려합니다.

분석:

반복 프로세스:

루트 노드 5를 입력합니다

뿌리 노드 5의 왼쪽 노드와 오른쪽 노드가 존재하는지 순서대로 판단한다. 왼쪽 노드가 존재하고 왼쪽 노드 4를 입력한다.오른쪽 노드가 존재하고 오른쪽 노드 8 입력;두 번째 층은 반복해서 끝난다

왼쪽에서 오른쪽으로 3층을 두루 다니기 때문에 노드 4를 먼저 판단해야 한다.왼쪽 노드가 존재하고 왼쪽 노드 11을 입력합니다.오른쪽 노드가 존재하지 않습니다

계속해서 오른쪽으로 3층을 훑어보고 노드 8을 판단한다.왼쪽 노드가 존재하고 왼쪽 노드 13 입력;오른쪽 노드가 존재하고 오른쪽 노드 4 입력;3층 반복 종료;

반복이 끝날 때까지 함께 올라가라.종합적으로 보면 우리는 노드가 저장된 순서에 따라 현재 노드의 좌우 노드가 존재하는지 판단하고 먼저 저장된 노드가 먼저 판단(선진 선출)하기 때문에 우리는 대열(queue)으로 두 갈래 나무의 너비 우선 검색을 실현한다

프로그래밍:

대기열 저장 루트 노드;

대열의 헤드 노드가 좌우 노드가 존재하는지 판단한다. 존재하고 노드를 대열에 넣는다.이때 헤드 결점의 좌우 노드는 저장 완료를 판단하고 대기열 헤드 결점을 삭제한다

같이 대기열의 모든 노드가 모두 판단이 끝났을 때 대기열은 비어 있고 반복적으로 끝난다

프로그램 구현(C/C++):

#include 
#include 
#include 
#include 

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector rightSideView(TreeNode *root) {
        queue q;
        vector result;
        q.push(root);
        while (!q.empty()) {
            if (q.front()->left) {
                q.push(q.front()->left);
            }
            if (q.front()->right) {
                q.push(q.front()->right);
            }
            result.push_back(q.front()->val);
            q.pop();
        }
        return result;
    }
};

int main() {
    TreeNode a(5);
    TreeNode b(4);
    TreeNode c(8);
    TreeNode d(11);
    TreeNode e(13);
    TreeNode f(4);
    TreeNode g(7);
    TreeNode h(2);
    TreeNode i(5);
    TreeNode j(1);
    a.left = &b;
    b.left = &d;
    d.left = &g;
    d.right = &h;
    a.right = &c;
    c.left = &e;
    c.right = &f;
    f.left = &i;
    f.right = &j;
    Solution s;
    vector result;
    result = s.rightSideView(&a);
    for (int i = 0; i < result.size(); i++) {
        printf("%d->", result[i]);
    }
    return 0;
}

결과:

5->4->8->11->13->4->7->2->5->1->