116. 填充每个节点的下一个右侧节点指针

题目描述

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

1
2
3
4
5
6


struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’#’ 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

提示：

树中节点的数量在 [0, 2¹² - 1] 范围内
-1000 <= node.val <= 1000

进阶：

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

解法一：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if nil == root {
        return root
    }
    var queue []*Node
    queue = append(queue, root)
    for len(queue) > 0 {
        cnt := len(queue)
        var prev *Node
        for cnt > 0 {
            cur := queue[0]
            queue = queue[1:]
            if prev != nil {
                prev.Next = cur
            }
            prev = cur
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
            cnt--
        }
    }
    return root
}

解法二：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    prevNodes := make(map[int]*Node)
    var dfs func(root *Node, depth int)
    dfs = func(root *Node, depth int) {
        if root == nil {
            return
        }
        if prev, has := prevNodes[depth]; has {
            prev.Next = root
        }
        prevNodes[depth] = root
        dfs(root.Left, depth+1)
        dfs(root.Right, depth+1)
    }
    dfs(root, 0)
    return root
}

解法三：最优解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    dummy := &Node{}
    up, down := root, dummy
    for up != nil && up.Left != nil {
        for up != nil {
            down.Next = up.Left
            down = down.Next
            down.Next = up.Right
            down = down.Next
            up = up.Next
        }
        up = dummy.Next
        down = dummy
    }
    return root
}