Populating Next Right Pointers in Each Node II

描述

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note: You may only use constant extra space.

For example,Given the following binary tree,

  1.          1
  2.        /  \
  3.       2    3
  4.      / \    \
  5.     4   5    7

After calling your function, the tree should look like:

  1.          1 -> NULL
  2.        /  \
  3.       2 -> 3 -> NULL
  4.      / \    \
  5.     4-> 5 -> 7 -> NULL

分析

要处理一个节点，可能需要最右边的兄弟节点，首先想到用广搜。但广搜不是常数空间的，本题要求常数空间。

注意，这题的代码原封不动，也可以解决 Populating Next Right Pointers in Each Node I.

递归版

  1. // Populating Next Right Pointers in Each Node II
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public void connect(TreeLinkNode root) {
  5.         if (root == null) return;
  7.         TreeLinkNode dummy = new TreeLinkNode(-1);
  8.         for (TreeLinkNode curr = root, prev = dummy;
  9.                 curr != null; curr = curr.next) {
  10.             if (curr.left != null){
  11.                 prev.next = curr.left;
  12.                 prev = prev.next;
  13.             }
  14.             if (curr.right != null){
  15.                 prev.next = curr.right;
  16.                 prev = prev.next;
  17.             }
  18.         }
  19.         connect(dummy.next);
  20.     }
  21. }

迭代版

  1. // Populating Next Right Pointers in Each Node II
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public void connect(TreeLinkNode root) {
  5.         while (root!= null ) {
  6.             TreeLinkNode next = null; // the first node of next level
  7.             TreeLinkNode prev = null; // previous node on the same level
  8.             for (; root != null; root = root.next) {
  9.                 if (next == null) next = root.left != null ? root.left : root.right;
  11.                 if (root.left != null) {
  12.                     if (prev != null) prev.next = root.left;
  13.                     prev = root.left;
  14.                 }
  15.                 if (root.right != null) {
  16.                     if (prev != null) prev.next = root.right;
  17.                     prev = root.right;
  18.                 }
  19.             }
  20.             root = next; // turn to next level
  21.         }
  22.     }
  23. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/populating-next-right-pointers-in-each-node-ii.html