题目描述（中等难度）

116. Populating Next Right Pointers in Each Node - 图1

116. Populating Next Right Pointers in Each Node - 图2

给定一个满二叉树，每个节点多了一个next指针，然后将所有的next指针指向它的右边的节点。并且要求空间复杂度是O(1)。

解法一 BFS

如果没有要求空间复杂度这道题就简单多了，我们只需要用一个队列做BFS，BFS参见 102 题。然后按顺序将每个节点连起来就可以了。

  1. public Node connect(Node root) {
  2.     if (root == null) {
  3.         return root;
  4.     }
  5.     Queue<Node> queue = new LinkedList<Node>();
  6.     queue.offer(root);
  7.     while (!queue.isEmpty()) {
  8.         int size = queue.size();
  9.         Node pre = null;
  10.         for (int i = 0; i < size; i++) {
  11.             Node cur = queue.poll();
  12.             //从第二个节点开始，将前一个节点的 pre 指向当前节点
  13.             if (i > 0) {
  14.                 pre.next = cur;
  15.             }
  16.             pre = cur;
  17.             if (cur.left != null) {
  18.                 queue.offer(cur.left);
  19.             }
  20.             if (cur.right != null) {
  21.                 queue.offer(cur.right);
  22.             }
  24.         }
  25.     }
  26.     return root;
  27. }

解法二 迭代

当然既然题目要求了空间复杂度，那么我们来考虑下不用队列该怎么处理。只需要解决三个问题就够了。

  • 每一层怎么遍历？

    之前是用队列将下一层的节点保存了起来。

    这里的话，其实只需要提前把下一层的next构造完成，到了下一层的时候就可以遍历了。

  • 什么时候进入下一层？

    之前是得到当前队列的元素个数，然后遍历那么多次。

    这里的话，注意到最右边的节点的next为null，所以可以判断当前遍历的节点是不是null。

  • 怎么得到每层开头节点？

    之前队列把当前层的所以节点存了起来，得到开头节点当然很容易。

    这里的话，我们额外需要一个变量把它存起来。

三个问题都解决了，就可以写代码了。利用三个指针，start 指向每层的开始节点，cur指向当前遍历的节点，pre指向当前遍历的节点的前一个节点。

116. Populating Next Right Pointers in Each Node - 图3

如上图，我们需要把 pre 的左孩子的 next 指向右孩子，pre 的右孩子的next指向cur的左孩子。

116. Populating Next Right Pointers in Each Node - 图4

如上图，当 cur 指向 null 以后，我们只需要把 pre 的左孩子的 next 指向右孩子。

  1. public Node connect(Node root) {
  2.     if (root == null) {
  3.         return root;
  4.     }
  5.     Node pre = root;
  6.     Node cur = null;
  7.     Node start = pre;
  8.     while (pre.left != null) {
  9.         //遍历到了最右边的节点，要将 pre 和 cur 更新到下一层，并且用 start 记录
  10.         if (cur == null) {
  11.             //我们只需要把 pre 的左孩子的 next 指向右孩子。
  12.             pre.left.next = pre.right;
  14.             pre = start.left;
  15.             cur = start.right;
  16.             start = pre;
  17.         //将下一层的 next 连起来，同时 pre、next 后移
  18.         } else {
  19.             //把 pre 的左孩子的 next 指向右孩子
  20.             pre.left.next = pre.right;
  21.             //pre 的右孩子的 next 指向 cur 的左孩子。
  22.             pre.right.next = cur.left;
  24.             pre = pre.next;
  25.             cur = cur.next;
  26.         }
  27.     }
  28.     return root;
  29. }

分享下 leetcode 的高票回答的代码，看起来更简洁一些，C++ 写的。

  1. void connect(TreeLinkNode *root) {
  2.     if (root == NULL) return;
  3.     TreeLinkNode *pre = root;
  4.     TreeLinkNode *cur = NULL;
  5.     while(pre->left) {
  6.         cur = pre;
  7.         while(cur) {
  8.             cur->left->next = cur->right;
  9.             if(cur->next) cur->right->next = cur->next->left;
  10.             cur = cur->next;
  11.         }
  12.         pre = pre->left;
  13.     }
  14. }

我的代码里的变量和他的变量对应关系如下。

  1. 我的 start    pre    cur
  2.       |       |      |
  3. 他的  pre     cur    cur.next

除了变量名不一样，算法本质还是一样的。

总

题目让我们初始化 next 指针，初始化过程中我们又利用到了next指针，很巧妙了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情