LeetCode 116 - Populating Next Right Pointers in Each Node

作者 QIFAN 日期 2016-12-30
LeetCode 116 - Populating Next Right Pointers in Each Node

原题链接:116. Populating Next Right Pointers in Each Node


题干

给普通二叉树的节点加一个新的指针 next ,指向其右边节点,若无右边节点,则指向 null

例子:
before

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

after

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

要求:
常数额外空间

前提:
假设是完全二叉树,即所有叶子都在同一层,每个父节点都有两个子节点。

思路

这题用递归做。只要观察出规律。

首先是 base case 。如果节点是 Null,就直接返回。
其次,连接每个节点的有节点意味着,如果它是左孩子,则连接对应的右孩子;如果它是右孩子,则连接它父节点对应右孩子的左孩子,也就是父节点的 next 。所以需要一个额外的父节点引用。
还有对于根节点,什么也不需要改变。

代码:

public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
TreeLinkNode parent = root;
connect(root.left, root);
connect(root.right, root);
}
public void connect(TreeLinkNode curr, TreeLinkNode parent) {
// base case
if (curr == null) {
return;
}
// 如果是左孩子,连接右孩子
if (parent.left == curr) {
curr.next = parent.right;
// 如果是右孩子,连接父节点 next 的左孩子。
} else {
if (parent.next != null) {
curr.next = parent.next.left;
}
}
connect(curr.left, curr);
connect(curr.right, curr);
}