题目描述（中等难度）

117. Populating Next Right Pointers in Each Node II - 图1

117. Populating Next Right Pointers in Each Node II - 图2

给定一个二叉树，然后每个节点有一个 next 指针，将它指向它右边的节点。和 116 题 基本一样，区别在于之前是满二叉树。

解法一 BFS

直接把 116 题 题的代码复制过来就好，一句也不用改。

利用一个栈将下一层的节点保存。通过pre指针把栈里的元素一个一个接起来。

  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.             if (i > 0) {
  13.                 pre.next = cur;
  14.             }
  15.             pre = cur;
  16.             if (cur.left != null) {
  17.                 queue.offer(cur.left);
  18.             }
  19.             if (cur.right != null) {
  20.                 queue.offer(cur.right);
  21.             }
  23.         }
  24.     }
  25.     return root;
  26. }

解法二

当然题目要求了空间复杂度，可以先到 116 题 看一下思路，这里在上边的基础上改一下。

我们用第二种简洁的代码，相对会好改一些。

  1. Node connect(Node root) {
  2.     if (root == null)
  3.         return root;
  4.     Node pre = root;
  5.     Node cur = null;
  6.     while (pre.left != null) {
  7.         cur = pre;
  8.         while (cur != null) {
  9.             cur.left.next = cur.right;
  10.             if (cur.next != null) {
  11.                 cur.right.next = cur.next.left;
  12.             }
  13.             cur = cur.next;
  14.         }
  15.         pre = pre.left;
  16.     }
  18.     return root;
  19. }

需要解决的问题还是挺多的。

  1. cur.left.next = cur.right;
  2. cur.right.next = cur.next.left;

之前的关键代码就是上边两句，但是在这道题中我们无法保证cur.left 或者 cur.right 或者 cur.next.left或者cur.next.right 是否为null。所以我们需要用一个while循环来保证当前节点至少有一个孩子。

  1. while (cur.left == null && cur.right == null) {
  2.     cur = cur.next; 
  3. }

这样的话保证了当前节点至少有一个孩子，然后如果一个孩子为 null，那么就可以保证另一个一定不为 null 了。

整体的话，就用了上边介绍的技巧，代码比较长，可以结合的看一下。

  1. Node connect(Node root) {
  2.     if (root == null)
  3.         return root;
  4.     Node pre = root;
  5.     Node cur = null;
  6.     while (true) {
  7.         cur = pre;
  8.         while (cur != null) {
  9.             //找到至少有一个孩子的节点
  10.             if (cur.left == null && cur.right == null) {
  11.                 cur = cur.next;
  12.                 continue;
  13.             }
  14.             //找到当前节点的下一个至少有一个孩子的节点
  15.             Node next = cur.next;
  16.             while (next != null && next.left == null && next.right == null) {
  17.                 next = next.next;
  18.                 if (next == null) {
  19.                     break;
  20.                 }
  21.             }
  22.             //当前节点的左右孩子都不为空，就将 left.next 指向 right
  23.             if (cur.left != null && cur.right != null) {
  24.                 cur.left.next = cur.right;
  25.             }
  26.             //要接上 next 的节点的孩子，所以用 temp 处理当前节点 right 为 null 的情况
  27.             Node temp = cur.right == null ? cur.left : cur.right;
  29.             if (next != null) {
  30.                 //next 左孩子不为 null，就接上左孩子。
  31.                 if (next.left != null) {
  32.                     temp.next = next.left;
  33.                 //next 左孩子为 null，就接上右孩子。
  34.                 } else {
  35.                     temp.next = next.right;
  36.                 }
  37.             }
  39.             cur = cur.next;
  40.         }
  41.         //找到拥有孩子的节点
  42.         while (pre.left == null && pre.right == null) {
  43.             pre = pre.next;
  44.             //都没有孩子说明已经是最后一层了
  45.             if (pre == null) {
  46.                 return root;
  47.             }
  48.         }
  49.         //进入下一层
  50.         pre = pre.left != null ? pre.left : pre.right;
  51.     } 
  52. }

解法三

参考 这里.-Concise.-Fast.-What’s-so-hard>)。

利用解法一的思想，我们利用 pre 指针，然后一个一个取节点，把它连起来。解法一为什么没有像解法二那样考虑当前节点为 null 呢？因为我们没有添加为 null 的节点，就是下边的代码的作用。

  1. if (cur.left != null) {
  2.     queue.offer(cur.left);
  3. }
  4. if (cur.right != null) {
  5.     queue.offer(cur.right);
  6. }

所以这里是一样的，如果当前节点为null不处理就可以了。

第二个问题，怎么得到每次的开头的节点呢？我们用一个dummy指针，当连接第一个节点的时候，就将dummy指针指向他。此外，之前用的pre指针，把它当成tail指针可能会更好理解。如下图所示：

117. Populating Next Right Pointers in Each Node II - 图3

cur 指针利用 next 不停的遍历当前层。

如果 cur 的孩子不为 null 就将它接到 tail 后边，然后更新tail。

当 cur 为 null 的时候，再利用 dummy 指针得到新的一层的开始节点。

dummy 指针在链表中经常用到，他只是为了处理头结点的情况，它并不属于当前链表。

代码就异常的简单了。

  1. Node connect(Node root) {
  2.     Node cur = root;
  3.     while (cur != null) {
  4.         Node dummy = new Node();
  5.         Node tail = dummy;
  6.         //遍历 cur 的当前层
  7.         while (cur != null) {
  8.             if (cur.left != null) {
  9.                 tail.next = cur.left;
  10.                 tail = tail.next;
  11.             }
  12.             if (cur.right != null) {
  13.                 tail.next = cur.right;
  14.                 tail = tail.next;
  15.             }
  16.             cur = cur.next;
  17.         }
  18.         //更新 cur 到下一层
  19.         cur = dummy.next;
  20.     }
  21.     return root;
  22. }

总

本来为了图方便，在 116 题 的基础上把解法二改了出来，还搞了蛮久，因为为 null 的情况太多了，不停的报空指针异常，最后终于理清了思路。但和解法三比起来实在是相形见绌了，解法三太优雅了，但其实这才是正常的思路，从解法一的做法产生灵感，利用 tail 指针将它们连起来。

windliang wechat

添加好友一起进步~

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

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