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)$。