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

2021-12-29 190 words One minute

Contents

題目敘述

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

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

解題流程

這題跟很多 tree 的題目一樣，可以用 BFS 或者 DFS 兩種方式去實現。

BFS

用 BFS 的解法，就是在每個 level 找到最左邊的 Node 當作開頭，往右開始每個節點都用 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 child->next 指向 right child。如果有 right child 就指向 next child->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;}();