leetcode 116
    https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
    116.png

    1. // BFS 实现
    2. func connect(root *Node) *Node {
    3.     if root == nil {
    4.         return root 
    5.     }
    6.     roott := root 
    7.     queue := []*Node{}
    8.     queue = append(queue,roott)
    9.     for len(queue) >0 {
    10.         length := len(queue) 
    11.         for length > 0 {
    12.             length-- 
    13.             roott = queue[0]
    14.             queue = queue[1:]
    15.             if roott.Left !=nil {
    16.                 queue = append(queue,roott.Left)
    17.             }
    18.             if roott.Right != nil {
    19.                 queue = append(queue,roott.Right)
    20.             }
    21.             if length ==0 {
    22.                 roott.Next = nil 
    23.             } else {
    24.                 roott.Next = queue[0]
    25.             }
    26.         }
    28.     }
    29.     return root 
    30. }
    32. // 递归
    33. func connect(root *Node) *Node {
    34.     if root == nil {
    35.         return nil
    36.     }
    37.     l := root.Left
    38.     r := root.Right
    39.     for l != nil {
    40.         l.Next = r //连接
    41.         l = l.Right //往右
    42.         r = r.Left //往左
    43.     }
    44.     connect(root.Left)
    45.     connect(root.Right)
    46.     return root
    47. }
    50. //迭代 空间复杂度O(1)
    51. func connect(root *Node) *Node {
    52.         if root == nil {
    53.         return nil
    54.     }
    55.    cur := root 
    56.    for cur != nil {
    57.        dummy := &Node{}  // 创建哑节点
    58.        pre := dummy 
    59.        for cur != nil {
    60.            if cur.Left != nil {
    61.                pre.Next = cur.Left 
    62.                pre = pre.Next 
    63.            }
    64.            if cur.Right != nil {
    65.                pre.Next = cur.Right 
    66.                pre = pre.Next 
    67.            }
    68.            cur = cur.Next 
    69.        }
    70.        cur = dummy.Next 
    71.    }
    72.    return root 
    73. }
    76. // 迭代   左节点向右，右节点向左
    79. func connect(root *Node) *Node {
    80.     if root == nil {
    81.         return nil
    82.     }
    83.     pre := root
    84.     for pre.Left != nil {
    85.         parent := pre
    86.         for parent != nil {
    87.             parent.Left.Next = parent.Right //左节点连接右节点
    88.             if parent.Next != nil {
    89.                 parent.Right.Next = parent.Next.Left //右节点 连接 邻居左节点
    90.             }
    91.             parent = parent.Next //同层移动
    92.         }
    93.         pre = pre.Left //移到下层
    94.     }
    95.     return root
    96. }

    leetcode 117
    https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
    117.png

    // BFS 
func connect(root *Node) *Node {
    if root == nil {
        return nil 
    }
    roott := root 
    queue := []*Node{} 
    queue = append(queue,roott)

    for len(queue) >0 {
        length := len(queue)
        for length >0 {
            length-- 
            cur := queue[0]
            queue = queue[1:]

            if cur.Left != nil {
                queue = append(queue,cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue,cur.Right)
            }
            if length >0 {
                cur.Next = queue[0]
            }

        }
    }
    return root 
}


//迭代 
func connect(root *Node) *Node {
    if root == nil {
        return nil 
    }
    cur := root

    for cur != nil {
        dummy := &Node{}
        pre := dummy 
        for cur != nil {
            if cur.Left != nil {
                pre.Next = cur.Left
                pre = pre.Next 
            }

            if cur.Right != nil {
                pre.Next = cur.Right
                pre = pre.Next
            }
            cur = cur.Next 
        }
        cur = dummy.Next 
    }
    return root 
}