No. 116 - Populating Next Right Pointers in Each Node

---

LeetCode 116 – Populating Next Right Pointers in Each Node

題目描述

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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.

---

這題的目的是把每個 node 的 next 指標指向右邊的 node。

對於每個 parent 的 left child 我們可以很簡單的就知道它的 next 就是 right child，因為是 perfect binary tree，有 left child 就會有 right child。但 right child 的 next 就不一定了，這取決於它的 parent 的 next 有沒有指向 node。若 parent 的 next 有指向別的 node，則 right child 的 next 就會指向 parent 的 next 所指向的 node 的 left child。若 parent 的next 為 NULL，則 right child 的 next 也就不會指向任何 node。所以接 next 的方法就像下面所寫的。

node->left->next = node->right;
if (node->next)
  node->right->next = node->next->left;

這個題目可以分別用 breadth first search 或 depth first search 的方法來解。

解法 1 Breadth First Search

BFS 的作法就是先把 Tree 每一層的 node 都做完才去做下一層，如下面的圖所示，BFS 會先把紅色路徑的 nodes 的 next 指標都指向對應的 node 接著才做藍色路徑。

其完整程式碼如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

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

BFS 是用 queue 來解，每一次的 iteration 我們就把走訪到的那一層的 node 由左至右的 push 進 queue 裡面，也就是程式碼的第 34 - 39 行。

因為每次從 queue 裡面拿出來的 node 它的 next 就是指向下一次要從 queue 裡面拿出來的 node，所以就不需要前面寫的演算法，只要每次都把 node 的 next 指向 queue 的最前面的 node。但同一層最後的 node 的 next 就不能指向 queue 的下一個 node，因為接下來的 node 就是下一層的 node。為了防止一層最後的 node 指到下一層的 node，我們會每一層開始找每個 node 的 next 時我們要先記住當前 queue 裡面有多少 node (第 30 行)。當確定不是最後一個 node 的時候才能找 next (第 34-35 行)。

另外，其實也可以不用 queue 而是用 recursive 的方法來解，recursive 的寫法如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

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

bfs 函式在做的事就是幫每一層的 nodes 找 next，而傳入的參數 node 是要找 next 那層的上一層最左邊的 node。而在第 22 行透過判斷 node 的 next 有沒有指向 node 來知道其 right child 的 next 需不需要指向其他 node。

解法 2 Depth First Search

DFS 並不會先把同一層的 node 都找到 next，而是只會先找當前 node 的 left child 跟 right child，接著就繼續往其 child 的 left child 跟 right 找 next 如下圖所示，先走完紅色路徑後，再走藍色，最後走綠色。這張圖看起來還是像先走完一層再走下一層，但如果 tree 再多一層的話，綠色路徑就會改成是先走 node 4 的 left child 跟 right child。

DFS 的完整程式碼如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
  Node* connect(Node* root) {
    if (!root)
      return root;
    stack<Node*> st;
    st.push(root);
    Node *node;
    while (!st.empty()) {
      node = st.top();
      st.pop();
      if (node->left) {
        node->left->next = node->right;
        if (node->next)
          node->right->next = node->next->left;
        st.push(node->right);
        st.push(node->left);
      }
    }
    return root;
  }
};

DFS 是用 stack 來解，每一次的 iteration 我們就將 stack 最上面的 node 的 left child 跟 right child 找出 next 要指向的 node (第 30 - 33 行) 接著再把 right child 跟 left child 依序放進 stack。因為 stack 是先進後出的特性，所以每次 iteration 一定會先往 left child 去做找 next 指向的 node 的處理，直到 left child 不存在才會往 right sibling 做 (因為這是 perfect binary tree 所以 left child 不存在 right child 就一定不存在)。

我們也可以不用 stack 來存 node，用 recursive 的方法來寫。每次呼叫 connect 就把 root 的 left child 跟 right child 的 next 指到對應的 node 或 NULL。接著就把其 left child 跟 right child 依序丟進下一次的 connect 如此遞迴。

完整程式碼如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

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

複雜度分析

時間複雜度上，因為都一定要走訪過所有的 nodes 所以是

$O(N)$。

空間複雜度上，BFS 不論是 recursive 或用 queue 都需要

$O(2^H)$，因為 queue 最多會存一整層的 nodes，而 recursive 的話函式 stack 也是。DFS 的解法的話，複雜度都是

$O(H)$。