填充每个结点的下一个右侧结点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

代码实现

思路一：

在二叉树层序遍历的基础上，对每一层进行右节点的连结，需判断右节点是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
    public Node connect(Node root){
        if(root==null) return null;
        Queue<Node> queue=new LinkedList<>();
        queue.add(root);
     
        while(queue.size()>0){//
            int n=queue.size();
            for(int i=0;i<n;i++){
                Node node=queue.poll();
                if(i<n-1){
                    node.next=queue.peek();
                }
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                
            }
        }
        return root;
    }
}

思路二：

1
2
3
4
5
6
7
8
9
10
11
12
13
//每个 node 左子树的 next , 就是 node 的右子树
//每个 node 右子树的 next, 就是 node next 的 左子树
public Node connect(Node root){
        dfs(root,null);
        return root;
    }
public void dfs(Node node,Node next){
    if(node.next!=null){
        node.next=next;
        dfs(node.left,node.right);
        dfs(node.right,node.next!=null? node.next.left:null);
    }
}