LeetCodeDay47 —— 填充同一层的兄弟节点★★☆

116. 填充同一层的兄弟节点

描述

给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。

说明

• 你只能使用额外常数空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
• 你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

示例

  struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
  }
  给定完美二叉树，
        1
      /  \
      2    3
    / \  / \
    4  5  6  7
  调用你的函数后，该完美二叉树变为：
        1 -> NULL
      /  \
      2 -> 3 -> NULL
    / \  / \
    4->5->6->7 -> NULL

思路

1. 一开始的想法是从节点出发，如果是左节点，则next是右节点，如果是右节点，则next是父节点next的左节点。整体是以单个节点为单元考虑的，需要区分左、右节点的情况，不容易变现为代码。
2. 往上，视野更宽些。以根节点+左右两个节点为单元考虑就清晰多了。一个单元内的左节点next是右节点，右节点的next是父节点next的左节点(没有就是NULL)。将三者放在一起考虑，递归就出来了。(参考)
3. 如果不考虑额外的空间，可以利用一个queue来实现对树的层次遍历BSF. 每个节点的next都指向queue中的下一个节点。
   1)小技巧，在每层最后一个元素后面加一个NULL
   2)这样不仅可以让最后一个元素直接指向NULL，还可以用于判断一层元素的遍历结束。

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解法的尾递归改为循环
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实现层次遍历
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 {  // 当前节点为空，即本层节点遍历完毕
        if (mQueue.size() == 0) return;
        mQueue.push(NULL); // 下一层节点都已装载完毕，加入一个NULL的标记
      }
    }
  }
};