乐趣区

关于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)。

退出移动版