P181 树节点的 next 指针

描述#

这个题目说的是，给你一棵满二叉树，每个树节点额外增加一个 next 指针，指向它右边的节点。一开始所有节点的 next 指针都为空，你要写一个函数处理这棵二叉树，使得所有节点的 next 指针都指向正确的节点。

注意，满二叉树中，所有叶子节点都在最后一层。并且除了叶子节点，所有其他节点都有两个子节点。

// 包含 next 指针的树节点定义
public class Node {
  public int val;
  public Node left, right, next;
}
比如说，给你的满二叉树是：
 0

/   

2     4
/ \   / 

6   8 10  12
一开始每个节点的 next 指针都为空。你要做的就是，让每个节点的 next 指针指向它右边的节点。对于每一层中最后一个节点，由于它右边没有节点，因此它的 next 指针仍然指向空即可。
  0 -> null

/     

2  ->   4 -> null
/ \     / 

6-> 8->10-> 12 -> null

代码#

public class AlgoCasts {

  class Node {
    public int val;
    public Node left, right, next;

    public Node(int val) {
      this.val = val;
    }

    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }

  // Time: O(n), Space: O(log(n))
  public Node connectRecursive(Node root) {
    if (root == null || root.left == null) return root;
    root.left.next = root.right;
    if (root.next != null)
      root.right.next = root.next.left;
    connectRecursive(root.left);
    connectRecursive(root.right);
    return root;
  }

  // Time: O(n), Space: O(1)
  public Node connectIterative(Node root) {
    if (root == null) return null;
    Node leftMost = root, p;
    while (leftMost.left != null) {
      p = leftMost;
      while (p != null) {
        p.left.next = p.right;
        if (p.next != null)
          p.right.next = p.next.left;
        p = p.next;
      }
      leftMost = leftMost.left;
    }
    return root;
  }

}