Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/
2 3
/ /
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/
2 -> 3 -> NULL
/ /
4->5->6->7 -> NULL
给定一棵二叉树，有一个next指针，将它们的每一层链接起来。只能使用常量额外空间，树是一棵完美二叉树。
将树的每一层节点用next串起来。这样每一层也会形成一个单链表。而每层的链表头，则是根的左孩子。利用双循环，外层循环，沿着根的左孩子，一直向下。内层循环，负责将下一层的节点串起来。即将自己右孩子放到左孩子的next上，而右孩子，则可通过自己的next指针，找到右邻居。
解法1: 递归
解法2: 迭代
Java: T: O(n), S: O(1)
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode level_start=root;
while(level_start!=null){
TreeLinkNode cur=level_start;
while(cur!=null){
if(cur.left!=null) cur.left.next=cur.right;
if(cur.right!=null && cur.next!=null) cur.right.next=cur.next.left;
cur=cur.next;
}
level_start=level_start.left;
}
}
}
Java:
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode node;
// 题中假设了输入的树是一棵完全叉树
// 第一个循环用来处理整个树
// root.left != null如果不用，则处理到最后第一个没有左右子树的结点会出错
while (root != null && root.left != null) {
// 每个root表示第一个层的第一个结点
// node记录每一个层的第一个结点
node = root;
// 处理每个层
while (node != null) {
// 表示连接的是同一个结点的下的两子结点
node.left.next = node.right;
// node不是某个层的最后一个结点
if (node.next != null) {
// 将这个结点的右子结点连接到这个结点的同层相邻结点的左子结点上
node.right.next = node.next.left;
}
// 移动到同层的下一个结点
node = node.next;
}
// 移动到下一层的第一个结点
root = root.left;
}
}
}
Python: Time: O(n), Space: O(1)
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
def __repr__(self):
if self is None:
return "Nil"
else:
return "{} -> {}".format(self.val, repr(self.next))
class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
head = root
while head:
prev, cur, next_head = None, head, None
while cur and cur.left:
cur.left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next
head = head.left
Python: Recursion, Time: O(n), Space: O(logn)
class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
if root is None:
return
if root.left:
root.left.next = root.right
if root.right and root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
C++:
void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode *pre = root;
TreeLinkNode *cur = NULL;
while(pre->left) {
cur = pre;
while(cur) {
cur->left->next = cur->right;
if(cur->next) cur->right->next = cur->next->left;
cur = cur->next;
}
pre = pre->left;
}
}
C++: Recursion, more than constant space
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
if (root->left) root->left->next = root->right;
if (root->right) root->right->next = root->next? root->next->left : NULL;
connect(root->left);
connect(root->right);
}
};
C++: Non-recursion, more than constant space
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
queue<TreeLinkNode*> q;
q.push(root);
q.push(NULL);
while (true) {
TreeLinkNode *cur = q.front();
q.pop();
if (cur) {
cur->next = q.front();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
} else {
if (q.size() == 0 || q.front() == NULL) return;
q.push(NULL);
}
}
}
};
C++: 用两个指针start和cur，其中start标记每一层的起始节点，cur用来遍历该层的节点
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
TreeLinkNode *start = root, *cur = NULL;
while (start->left) {
cur = start;
while (cur) {
cur->left->next = cur->right;
if (cur->next) cur->right->next = cur->next->left;
cur = cur->next;
}
start = start->left;
}
}
};
类似题目：
[LeetCode] 117. Populating Next Right Pointers in Each Node II 每个节点的右向指针 II