The first question is Fill in the next right node pointer for each node
subject
Their thinking
Because the operation is at the same level , This problem can also be seen as a variant of sequence traversal ,
Only in the process of sequence traversal , Join the cascade of nodes at each level 、
Code
func connect(root *Node) *Node {
if root == nil {
return root
}
// Initialize the queue and add the first layer node to the queue , Root node
queue := []*Node{root}
// The number of layers of loop iteration
for len(queue) > 0 {
tmp := queue
queue = nil
// Traverse all nodes in this layer
for i, node := range tmp {
// Connect
if i+1 < len(tmp) {
node.Next = tmp[i+1]
}
// Expand the next level of nodes
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
// Return root node
return root
}
Complexity analysis
Time complexity ：O(N). Each node will be accessed once and only once , That is, pop up from the queue , And establish next The pointer .
Spatial complexity ：O(N). This is a perfect binary tree , Its last level contains N/2 Nodes . The breadth of traversal depends on the number of elements at the highest level . In this case, the space complexity is O(N)
Optimize
BFS The array used can be replaced by the connected upper node 
func connect(root *Node) *Node {
if root == nil {
return root
}
// Each cycle starts from the leftmost node of the layer
for leftmost := root; leftmost.Left != nil; leftmost = leftmost.Left {
// adopt Next Traverse this layer of nodes , Update nodes for the next layer Next The pointer
for node := leftmost; node != nil; node = node.Next {
// The left node points to the right node
node.Left.Next = node.Right
// The right node points to the next left node
if node.Next != nil {
node.Right.Next = node.Next.Left
}
}
}
// Return root node
return root
}
author ：LeetCode-Solution
link ：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/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .The second question is Binary search tree k Small elements
subject
Their thinking
The properties of binary search tree are
The value of the left subtree is less than the root node , The value of the right subtree is greater than the root node
Thus we can see that , The middle order traversal sequence of a binary search tree is an ordered sequence arranged from small to large
You can easily get one of them k Small elements
Code
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
}
}Complexity analysis
Time complexity ：O(H+k), among HH Is the height of the tree . Before starting traversal , We need to O(H) Reach the leaf node . When the tree is a balanced tree , Minimum time complexity O(logN+k); When the tree is a linear tree （ Each node in the tree has only one child node or no child node ） when , Maximum time complexity O(N+k).
Spatial complexity ：O(H), The stack needs to store at most H Elements . When the tree is a balanced tree , Space complexity is minimized O(logN); When the tree is a linear tree , Space complexity maximizes O(N)
Optimize （ understand ）
