第一题 填充每个节点的下一个右侧节点指针
题目
解题思路
因为是在同一档次的操作，本题也可看作为层序遍历的变种，
只须要在层序遍历的过程中，退出每一档次节点的串联即可、
代码
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)