leetcode-填充同一层的兄弟节点Ⅱ

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

给定一个二叉树

struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

说明:

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例:

给定二叉树，

1
/ \
2 3
/ \ \
4 5 7

调用你的函数后，该二叉树变为：

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

第一道题是：leetcode-每个节点的右向指针（填充同一层的兄弟节点）

我们依然可以使用层序遍历的方法，为每个结点添加next指针。

但是时间复杂度不满足要求。

public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)return ;
Queue<TreeLinkNode> q=new LinkedList();
q.add(root);
while(!q.isEmpty()){
int size=q.size();
for(int i=;i<size;i++){
TreeLinkNode temp=q.peek();q.poll();
if(i<size-)temp.next=q.peek();
if(temp.left!=null)q.add(temp.left);
if(temp.right!=null)q.add(temp.right);
}
}
}

将第一题的递归方法进行改造：

比如该二叉树

1
/ \
2 3
/ \ \
4 5 7
\ /\
914 15
/ \
18 19

遍历的顺序为：14->15 2->3 5->7 4->5 9->14 18->19

每次先处理结点的右子树，递归到叶子结点（没有左子树和右子树）。然后返回上一层，递归处理左子树。

类似于前序遍历的镜像： trave(root.right) ;

trave(root.left);

对每一层结点的处理可以通过tem=tem.next来进行跳转。

得到如下方法：

public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)return;
TreeLinkNode tem=root;
//处理root左子树的指针
if(root.left!=null){
if(root.right!=null){
root.left.next=root.right;
}
//处理root.left.next的指向
while(tem.next!=null&&root.left.next==null){
tem=tem.next;//tem可以在同一层结点进行跳转
if(tem.left!=null)root.left.next=tem.left;
else if(tem.right!=null)root.left.next=tem.right;
} }
//处理root右子树的指针
if(root.right!=null){
//处理root.right.next的指向
while(tem.next!=null&&root.right.next==null){
tem=tem.next;//tem可以在同一层结点进行跳转
if(tem.left!=null)root.right.next=tem.left;
else if(tem.right!=null)root.right.next=tem.right;
} } connect(root.right);
connect(root.left);
}
}