617. 合并二叉树

解题思路：递归函数，不断把两个点相加，边界范围为他们在递归的下一个节点为空，称为上一个节点左或右

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }

    if root2 == nil {
        return root1
    }

    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)

    return root1
}

时间复杂度：O(min(m,n))O(min(m,n))，其中 mm 和 nn 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点数不会超过较小的二叉树的节点数。

空间复杂度：O(min(m,n))O(min(m,n))，其中 mm 和 nn 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

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

解题思路：这个是二叉树层次遍历

步骤如下

1、先父节点的左边开始，左节点连接右节点，

2、父节点的相邻节点在开始

3、重复1，2直到走完左节点

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    leftNode := root

    for leftNode.Left != nil {
        node := leftNode

        // 遍历层
        for node != nil {
            // 左右节点连接
            node.Left.Next = node.Right

            if node.Next != nil {
                node.Right.Next = node.Next.Left
            }
            
            node = node.Next
        }

        leftNode = leftNode.Left
    }

    return root
}
时间复杂度：O(N)，每个节点只访问一次。
空间复杂度：O(1)，不需要存储额外的节点。