NO.116 各ノードの次の右側ポインタを埋める

完全二分木が与えられます。この木はすべての葉ノードが同じレベルにあり、各親ノードが2つの子ノードを持つ特徴があります。二分木は以下のように定義されます：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

各ノードのnextポインタを、その次の右側のノードを指すように設定してください。次の右側のノードが見つからない場合は、nextポインタをNULLに設定します。

初期状態では、すべてのnextポインタはNULLに設定されています。

例1：

<strong>入力：</strong>root = [1,2,3,4,5,6,7]
<strong>出力：</strong>[1,#,2,3,#,4,5,6,7,#]
<strong>説明：</strong>与えられた二分木は図Aのようになっており、関数は各ノードのnextポインタを、その次の右側ノードを指すように設定する必要があります（図B参照）。シリアライズされた出力はレベル順走査の順序で並べられ、同一レベルのノードはnextポインタで接続され、'#'は各レベルの終わりを示します。

例2:

<strong>入力：</strong>root = []
<strong>出力：</strong>[]

この問題の難しさは、各ノードのnextポインタを、その次の右側ノードを指すように設定することにあります。次のノードのポインタをどのように取得するか、まだ次のノードを走査していないのに、どうやってそのポインタを取得できるでしょうか？

ここでの考え方は、前のノードのポインタを保存し、そのnextポインタを現在のノードに設定することです。自然な考え方とは少し異なる、巧妙な方法ですね。

前のノードの変数を使用するため、ルートノードには前のノードがないことに注意する必要があります。

以下に完全なコードを示します。

class Solution {
public:
    Node* connect(Node* root) {
        // ノードを格納するキューを用意
        queue nodeQueue;
        if (root != nullptr) {
            nodeQueue.push(root);
        }

        // キューが空になるまで処理を続ける
        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size(); // 現在のレベルのノード数を記録
            Node* previousNode = nullptr;    // 前のノードを指すポインタ

            // 現在のレベルのすべてのノードを処理
            for (int i = 0; i < levelSize; ++i) {
                Node* currentNode = nodeQueue.front();
                nodeQueue.pop();

                // レベルの最初のノードでない場合、前のノードのnextを現在のノードに設定
                if (previousNode != nullptr) {
                    previousNode->next = currentNode;
                }

                // 前のノードを更新
                previousNode = currentNode;

                // 子ノードをキューに追加
                if (currentNode->left != nullptr) {
                    nodeQueue.push(currentNode->left);
                }
                if (currentNode->right != nullptr) {
                    nodeQueue.push(currentNode->right);
                }
            }
            // レベルの最後のノードのnextをNULLに設定
            if (previousNode != nullptr) {
                previousNode->next = nullptr;
            }
        }
        return root;
    }
};

NO.117 各ノードの次の右側ポインタを埋めるII

二分木が与えられます：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

各ノードのnextポインタを、その次の右側のノードを指すように設定してください。次の右側のノードが見つからない場合は、nextポインタをNULLに設定します。

初期状態では、すべてのnextポインタはNULLに設定されています。

例1：

<strong>入力</strong>：root = [1,2,3,4,5,null,7]
<strong>出力：</strong>[1,#,2,3,#,4,5,7,#]
<strong>説明：</strong>与えられた二分木は図Aのようになっており、関数は各ノードのnextポインタを、その次の右側ノードを指すように設定する必要があります（図B参照）。シリアライズされた出力はレベル順走査の順序で並べられ（nextポインタで接続）、'#'は各レベルの末尾を示します。

例2:

<strong>入力：</strong>root = []
<strong>出力：</strong>[]

この問題は「二分木」とされていますが、116番の問題は「完全二分木」と言っています。しかし、アルゴリズム的には全く同じで、同じコードと同じロジックで解くことができます。

以下に完全なコードを示します。

class Solution {
public:
    Node* connect(Node* root) {
        queue nodeQueue;
        if (root != nullptr) {
            nodeQueue.push(root);
        }

        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();
            Node* previousNode = nullptr;

            for (int i = 0; i < levelSize; ++i) {
                Node* currentNode = nodeQueue.front();
                nodeQueue.pop();

                if (previousNode != nullptr) {
                    previousNode->next = currentNode;
                }

                previousNode = currentNode;

                if (currentNode->left != nullptr) {
                    nodeQueue.push(currentNode->left);
                }
                if (currentNode->right != nullptr) {
                    nodeQueue.push(currentNode->right);
                }
            }
            if (previousNode != nullptr) {
                previousNode->next = nullptr;
            }
        }
        return root;
    }
};

NO.104 二分木の最大深度

二分木rootが与えられた場合、その最大深度を返してください。

二分木の最大深度とは、根ノードから最も遠い葉ノードまでの最長パス上のノード数を指します。

例1：

<strong>入力：</strong>root = [3,9,20,null,null,15,7]
<strong>出力：</strong>3

例2：

<strong>入力：</strong>root = [1,null,2]
<strong>出力：</strong>2

以下に完全なコードを示します。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue nodeQueue;
        int maxDepth = 0;

        if (root != nullptr) {
            nodeQueue.push(root);
        }

        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();

            // 現在のレベルのすべてのノードを処理
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* currentNode = nodeQueue.front();
                nodeQueue.pop();

                // 子ノードをキューに追加
                if (currentNode->left != nullptr) {
                    nodeQueue.push(currentNode->left);
                }
                if (currentNode->right != nullptr) {
                    nodeQueue.push(currentNode->right);
                }
            }
            // 1レベルの処理が終わるたびに深度をインクリメント
            maxDepth++;
        }
        return maxDepth;
    }
};

NO.111 二分木の最小深度

二分木が与えられた場合、その最小深度を見つけてください。

最小深度とは、根ノードから最も近い葉ノードまでの最短パス上のノード数を指します。

説明：葉ノードとは、子ノードを持たないノードを指します。

例1：

<strong>入力：</strong>root = [3,9,20,null,null,15,7]
<strong>出力：</strong>2

例2：

<strong>入力：</strong>root = [2,null,3,null,4,null,5,null,6]
<strong>出力：</strong>5

以下に完全なコードを示します。

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue nodeQueue;
        int currentDepth = 0;

        if (root != nullptr) {
            nodeQueue.push(root);
        }

        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();
            currentDepth++; // 深度をインクリメント

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* currentNode = nodeQueue.front();
                nodeQueue.pop();

                // 葉ノードが見つかった場合、その深度を返す
                if (currentNode->left == nullptr && currentNode->right == nullptr) {
                    return currentDepth;
                }

                // 子ノードをキューに追加
                if (currentNode->left != nullptr) {
                    nodeQueue.push(currentNode->left);
                }
                if (currentNode->right != nullptr) {
                    nodeQueue.push(currentNode->right);
                }
            }
        }
        return 0;
    }
};