关于golang:golangleetcode中级填充每个节点的下一个右侧节点指针二叉搜索树中第k小的元素

第一题 填充每个节点的下一个右侧节点指针

题目

解题思路

因为是在同一档次的操作，本题也可看作为层序遍历的变种，
只须要在层序遍历的过程中，退出每一档次节点的串联即可、

代码

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

    // 初始化队列同时将第一层节点退出队列中，即根节点
    queue := []*Node{root}

    // 循环迭代的是层数
    for len(queue) > 0 {
        tmp := queue
        queue = nil

        // 遍历这一层的所有节点
        for i, node := range tmp {
            // 连贯
            if i+1 < len(tmp) {node.Next = tmp[i+1]
            }

            // 拓展下一层节点
            if node.Left != nil {queue = append(queue, node.Left)
            }
            if node.Right != nil {queue = append(queue, node.Right)
            }
        }
    }

    // 返回根节点
    return root
}

复杂度剖析

工夫复杂度：O(N)。每个节点会被拜访一次且只会被拜访一次，即从队列中弹出，并建设 next 指针。

空间复杂度：O(N)。这是一棵完满二叉树，它的最初一个层级蕴含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种状况下空间复杂度为 O(N)

优化

BFS 应用的数组能够用已连贯的下层节点来代替

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

    // 每次循环从该层的最左侧节点开始
    for leftmost := root; leftmost.Left != nil; leftmost = leftmost.Left {
        // 通过 Next 遍历这一层节点，为下一层的节点更新 Next 指针
        for node := leftmost; node != nil; node = node.Next {
            // 左节点指向右节点
            node.Left.Next = node.Right

            // 右节点指向下一个左节点
            if node.Next != nil {node.Right.Next = node.Next.Left}
        }
    }

    // 返回根节点
    return root
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

第二题 二叉搜寻树中第 k 小的元素

题目

解题思路

二叉搜寻树的性质为

左子树的值小于根节点，右子树的值大于根节点

由此可知，二叉搜寻树的中序遍历序列即为从小到大排列的有序序列

便可轻易获取其中第 k 小的元素

代码

func kthSmallest(root *TreeNode, k int) int {stack := []*TreeNode{}
    for {
        for root != nil {stack = append(stack, root)
            root = root.Left
        }
        stack, root = stack[:len(stack)-1], stack[len(stack)-1]
        k--
        if k == 0 {return root.Val}
        root = root.Right
    }
}

复杂度剖析

工夫复杂度：O(H+k)，其中 HH 是树的高度。在开始遍历之前，咱们须要 O(H) 达到叶结点。当树是均衡树时，工夫复杂度获得最小值 O(logN+k)；当树是线性树（树中每个结点都只有一个子结点或没有子结点）时，工夫复杂度获得最大值 O(N+k)。

空间复杂度：O(H)，栈中最多须要存储 H 个元素。当树是均衡树时，空间复杂度获得最小值 O(logN)；当树是线性树时，空间复杂度获得最大值 O(N)

优化（理解）