关于golang:golangleetcode初级二叉树的层序遍历将有序数组转化为二叉搜索树

第一题

题目信息

解题思路

层序遍历二叉树，显然广搜更为高效
广搜的流程如图

因而咱们须要领有一个队列记录搜寻的节点状况

我很道歉
素朴的思路过于简单
我并不能很好的把他展现进去





让咱们学习优化一下解题思路

代码

func levelOrder(root *TreeNode) [][]int {ret := [][]int{}
    if root == nil {return ret}
    q := []*TreeNode{root}
    for i := 0; len(q) > 0; i++ {ret = append(ret, []int{})
        p := []*TreeNode{}
        for j := 0; j < len(q); j++ {node := q[j]
            ret[i] = append(ret[i], node.Val)
            if node.Left != nil {p = append(p, node.Left)
            }
            if node.Right != nil {p = append(p, node.Right)
            }
        }
        q = p
    }
    return ret
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

复杂度剖析

工夫复杂度：每个点进队出队各一次，故渐进工夫复杂度为 O(n)。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

第二题 将有序数组转化为二叉搜寻树

题目信息

解题思路

代码

func sortedArrayToBST(nums []int) *TreeNode {return helper(nums, 0, len(nums) - 1)
}

func helper(nums []int, left, right int) *TreeNode {
    if left > right {return nil}
    mid := (left + right) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = helper(nums, left, mid - 1)
    root.Right = helper(nums, mid + 1, right)
    return root
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

复杂度剖析

工夫复杂度：O(n)，其中 n 是数组的长度。每个数字只拜访一次。

空间复杂度：O(logn)，其中 nn 是数组的长度。空间复杂度不思考返回值，因而空间复杂度次要取决于递归栈的深度，递归栈的深度是 O(logn)。