leetcode 116. Populating Next Right Pointers in Each Node [Medium]

題目敘述

給定一個 perfect binary tree，定義 next 指標，root->next 為空，每個節點的 left child 的 next 為 right child。每個節點 right child 的 next 為該節點 next 的 left child。

用中文有點難表達，直接看圖吧。

解題流程

這題和許多 tree 題一樣，可以用 BFS 或 DFS 兩種方式實現。

BFS

BFS 解法是每個 level 找到最左邊的節點作為起點，依序用 next 指標把同層所有節點串起來。

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        
        queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            Node *curr;
            const int qsize = q.size();
            for (int i = 0; i < qsize; ++i) {
                Node *n = q.front();
                q.pop();
                
                if (i == 0) {
                    curr = n;
                } else {
                    curr->next = n;
                    curr = curr->next;
                }
                if (n->left) q.push(n->left);
                if (n->right) q.push(n->right);
            }
            
        }
        return root;
    }
};

DFS

DFS 解法是走訪每個節點：若有 left child，就讓 left->next 指向 right child；若有 right child，就讓 right->next 指向 node->next->left。由於題目保證是 perfect binary tree，left child 存在就不需要另外確認 right child 是否為 nullptr。

class Solution {
public:
    Node* connect(Node *root) {
        _connect(root);
        return root;
    }
    
    void _connect(Node *root) {
        if (!root) return;
        
        if (root->left) {
            root->left->next = root->right;
            if (root->next) {
                root->right->next = root->next->left;
            }
        }

        _connect(root->left);
        _connect(root->right);
    }
};

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();