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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii
• 标签: bfs

解法一: bfs

go

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

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    queue := []*Node{root}
    for len(queue) > 0 {
        length := len(queue)
        var pre *Node
        for i := 0; i < length; i++ {
            node := queue[i]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            if i > 0 {
                pre.Next = node
            }
            pre = node
        }
        queue = queue[length:]
    }
    return root
}

解法二: 利用 Next 指针

go

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

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    cur := root
    for cur != nil {
        linkNodeRoot := &Node{Val: -1}
        curLinkNode := linkNodeRoot
        for cur != nil {
            if cur.Left != nil {
                curLinkNode.Next = cur.Left
                curLinkNode = curLinkNode.Next
            }
            if cur.Right != nil {
                curLinkNode.Next = cur.Right
                curLinkNode = curLinkNode.Next
            }
            cur = cur.Next
        }
        cur = linkNodeRoot.Next
    }
    return root
}