📑 题目：116. 填充每个节点的下一个右侧节点指针

🚀 本题 LeetCode 传送门

题目大意

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

React JSX

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

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

解题思路

  • 本质上是二叉树的层序遍历，基于广度优先搜索，将每层的节点放入队列，并遍历队列进行连接。

代码

  1. package leetcode
  3. type Node struct {
  4.  Val   int
  5.  Left  *Node
  6.  Right *Node
  7.  Next  *Node
  8. }
  10. //解法一：迭代
  11. func connect(root *Node) *Node {
  12.  if root == nil {
  13.   return root
  14.  }
  15.  q := []*Node{root}
  16.  for len(q) > 0 {
  17.   var p []*Node
  18.   // 遍历这一层的所有节点
  19.   for i, node := range q {
  20.    if i+1 < len(q) {
  21.     node.Next = q[i+1]
  22.    }
  23.    if node.Left != nil {
  24.     p = append(p, node.Left)
  25.    }
  26.    if node.Right != nil {
  27.     p = append(p, node.Right)
  28.    }
  29.   }
  30.   q = p
  31.  }
  32.  return root
  33. }
  35. // 解法二 递归
  36. func connect2(root *Node) *Node {
  37.  if root == nil {
  38.   return nil
  39.  }
  40.  connectTwoNode(root.Left, root.Right)
  41.  return root
  42. }
  44. func connectTwoNode(node1, node2 *Node) {
  45.  if node1 == nil || node2 == nil {
  46.   return
  47.  }
  48.  node1.Next = node2
  49.  connectTwoNode(node1.Left, node1.Right)
  50.  connectTwoNode(node2.Left, node2.Right)
  51.  connectTwoNode(node1.Right, node2.Left)
  52. }