给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
复杂度分析

  • 时间复杂度：O(N)。每个节点会被访问一次且只会被访问一次，即从队列中弹出，并建立 next 指针。

  • 空间复杂度：O(N)。这是一棵完美二叉树，它的最后一个层级包含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种情况下空间复杂度为 O(N)。

    1. //bfs，层次遍历的写法
    2. func connect(root *Node) *Node {
    3.   if root == nil {
    4.       return root
    5.   }
    7.   queue := []*Node{root}          //1,初始化队列
    9.   for len(queue) > 0 {            //2,迭代层数=队列长度，横着的每层的数字
    10.       tmp := queue
    11.       queue = nil 
    13.       for i , node := range tmp {     //3,遍历这层所有节点
    14.           if i < len(tmp) - 1 {       //4,建立链表指针
    15.               node.Next = tmp[i+1]
    16.           }
    18.           if node.Left != nil {       //5，拓展下一个节点
    19.               queue = append(queue, node.Left)
    20.           }
    21.           if node.Right != nil {
    22.               queue = append(queue, node.Right)
    23.           }
    24.       }
    25.   }
    26.   return root
    27. }

    算法

  1. 从根节点开始，由于第 0 层只有一个节点，所以不需要连接，直接为第 11 层节点建立 next 指针即可。该算法中需要注意的一点是，当我们为第 NN 层节点建立next 指针时，处于第 N-1 层。当第 NN 层节点的 next 指针全部建立完成后，移至第 N 层，建立第 N+1 层节点的next 指针。
  2. 遍历某一层的节点时，这层节点的 next 指针已经建立。因此我们只需要知道这一层的最左节点，就可以按照链表方式遍历，不需要使用队列。

复杂度分析

  • 时间复杂度：O(N)，每个节点只访问一次。

  • 空间复杂度：O(1)，不需要存储额外的节点。

    //使用已建立的 next 指针
func connect(root *Node) *Node {
  if root == nil {
      return root
  }

  //1,从每层最左侧开始循环,前进每层的node
  for leftmost := root ; leftmost.Left != nil ; leftmost = leftmost.Left {

      //2,通过Next指针遍历n-1层，为第n层更新指针，前进node的Next
      for node := leftmost; node != nil; node = node.Next {
          node.Left.Next = node.Right         //3,有共同父节点的，下一层的左next=右
          if node.Next != nil {               //4，没有共同父节点，且没到最后一位的
              node.Right.Next = node.Next.Left    //下一层右next= 上层父节点下一位的左子节点
          }
      }
  }
  return root
}

思路

首先，每个节点的next原本就指向null。

  • 对于每个节点root，它的左孩子的next应改为指向它的右孩子（左右孩子肯定存在）。
  • 它的右孩子的next怎么找到右邻居呢？
    • 只要root.next存在（只要爸爸有右邻居），就能保证root.right有右邻居，让root.right.next指向root.next.left。image.png
  • 递归从上往下，先处理当前节点，再处理它的左、右子树中的节点——前序遍历。
  • 何时结束递归？当遍历到叶子节点，它没有孩子，不用修改孩子的next指向 ```go //dfs，递归写法 func connect(root Node) Node { if root == nil {
      return root
    } return modify(root) //1,递归函数，重复执行 }

func modify(root Node) Node { if root.Left == nil && root.Right == nil { //2，递归结束条件，没有兄弟节点了 return root } root.Left.Next = root.Right //3,有共同父节点的指针
if root.Next != nil { root.Right.Next = root.Next.Left //无共同父节点的指针
}

modify(root.Left)                            //4,递归的中间过程，循环调用下一个左右子节点
modify(root.Right)
return root

} ```

复盘总结

对于整棵树的根节点，它的next是对的，不用修改。
下面的子节点的next是要修改的。所以可以用 DFS，从上往下去修改。
左孩子的next肯定要修改，右孩子的next可能要修改。
后者的修改，需要有一个前提——自己的next要存在，右孩子才能找到右邻居。