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
思路：一层一层的连接，同一个父节点的左子树的邻居是其父节点的右子树 父节点右子树的邻居是 父节点邻居的左子树
我用的递归
void connect(TreeLinkNode *root) {
if(root == NULL) return;
TreeLinkNode * parent = root;
TreeLinkNode * cur = parent->left;
while(parent != NULL && cur != NULL)
{
cur = cur->next = parent->right; //左子树的邻居是同一个parent的右子树
cur->next = (parent->next == NULL) ? NULL : parent->next->left; //右子树的邻居 是parent的邻居的左子树
parent = parent->next;
cur = (parent == NULL) ? NULL : parent->left;
}
connect(root->left); //连接下一层
}
大神的非递归代码：外面加一圈对层循环
void connect(TreeLinkNode *root) {
if(!root)
return;
while(root -> left)
{
TreeLinkNode *p = root;
while(p)
{
p -> left -> next = p -> right;
if(p -> next)
p -> right -> next = p -> next -> left;
p = p -> next;
}
root = root -> left;
}
}
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
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
思路：非完全二叉树。关键是每一层要判断邻居是哪一个，每层的第一个有数字的位置也要定位。
我的代码，根据上一题的思路，用的非递归。对父节点左右子树都空，左子树空，右子树空，都非空分类处理。
void connect2(TreeLinkNode *root) {
if(root == NULL) return;
TreeLinkNode * newroot = root;
while(newroot != NULL) //对层循环
{
TreeLinkNode * p = newroot; //当前层父节点推进
TreeLinkNode * cur = NULL; //当前连接层当前指针位置
newroot = NULL; //下一层第一个父节点的位置
while(p != NULL)
{
if(p->left == NULL && p->right == NULL);
else if(p->left == NULL)
{
if(cur == NULL)
newroot = cur = p->right;
else
cur = cur->next = p->right;
}
else if(p->right == NULL)
{
if(cur == NULL)
newroot = cur = p->left;
else
cur = cur->next = p->left;
}
else
{
if(cur == NULL)
newroot = cur = p->left;
else
cur = cur->next = p->left;
cur = cur->next = p->right;
}
p = p->next;
}
}
}
大神的代码，处理的时候只要分左子树是否空，和右子树是否空即可。不需要分那么多情况。
public class Solution {
public void connect(TreeLinkNode root) {
while(root != null){
TreeLinkNode tempChild = new TreeLinkNode(); //该层的伪头结点，方便定位下一层第一个值的位置
TreeLinkNode currentChild = tempChild; //这两个值不用每次分配，在外面分配，内部循环使用即可
while(root!=null){ //只分两种情况就行了
if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
root = root.next;
}
root = tempChild.next;
}
}
}