116. 填充同一層的兄弟節(jié)點

描述

給定一個二叉樹，填充它的每個 next 指針，讓這個指針指向其下一個右側(cè)節(jié)點。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL。 初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

說明

• 你只能使用額外常數(shù)空間。
• 使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度。
• 你可以假設(shè)它是一個完美二叉樹（即所有葉子節(jié)點都在同一層，每個父節(jié)點都有兩個子節(jié)點）。

示例

  struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
  }
  給定完美二叉樹，
        1
      /  \
      2    3
    / \  / \
    4  5  6  7
  調(diào)用你的函數(shù)后，該完美二叉樹變?yōu)椋?        1 -> NULL
      /  \
      2 -> 3 -> NULL
    / \  / \
    4->5->6->7 -> NULL

思路

1. 一開始的想法是從節(jié)點出發(fā)，如果是左節(jié)點，則next是右節(jié)點，如果是右節(jié)點，則next是父節(jié)點next的左節(jié)點。整體是以單個節(jié)點為單元考慮的，需要區(qū)分左、右節(jié)點的情況，不容易變現(xiàn)為代碼。
2. 往上，視野更寬些。以根節(jié)點+左右兩個節(jié)點為單元考慮就清晰多了。一個單元內(nèi)的左節(jié)點next是右節(jié)點，右節(jié)點的next是父節(jié)點next的左節(jié)點(沒有就是NULL)。將三者放在一起考慮，遞歸就出來了。(參考)
3. 如果不考慮額外的空間，可以利用一個queue來實現(xiàn)對樹的層次遍歷BSF. 每個節(jié)點的next都指向queue中的下一個節(jié)點。
   1)小技巧，在每層最后一個元素后面加一個NULL
   2)這樣不僅可以讓最后一個元素直接指向NULL，還可以用于判斷一層元素的遍歷結(jié)束。

class Solution_116_01 {
 public:
  void connect(TreeLinkNode* root) {
    if (!root) return;
    if (root->left) root->left->next = root->right;
    if (root->right) root->right->next = root->next ? root->next->left : NULL;
    connect(root->left);
    connect(root->right);
  }
};
// 將01解法的尾遞歸改為循環(huán)
class Solution_116_02 {
 public:
  void connect(TreeLinkNode* root) {
    if (!root) return;
    stack<TreeLinkNode*> mStack;
    mStack.push(root);
    while (!mStack.empty()) {
      TreeLinkNode* node = mStack.top();
      mStack.pop();
      if (node->right) {
        node->right->next = node->next ? node->next->left : NULL;
        mStack.push(node->right);
      }
      if (node->left) {
        node->left->next = node->right;
        mStack.push(node->left);
      }
    }
  }
};
// 利用queue實現(xiàn)層次遍歷
class Solution_116_03 {
 public:
  void connect(TreeLinkNode* root) {
    if (!root) return;
    queue<TreeLinkNode*> mQueue;
    mQueue.push(root);
    mQueue.push(NULL);
    while (true) {
      TreeLinkNode* node = mQueue.front();
      mQueue.pop();
      if (node) {
        node->next = mQueue.front();
        if (node->left) mQueue.push(node->left);
        if (node->right) mQueue.push(node->right);
      } else {  // 當前節(jié)點為空，即本層節(jié)點遍歷完畢
        if (mQueue.size() == 0) return;
        mQueue.push(NULL); // 下一層節(jié)點都已裝載完畢，加入一個NULL的標記
      }
    }
  }
};