循环右移二叉树。
现有一棵个节点构成的二叉树，请你将每一层的节点向右循环位移位。某层向右位移一位(即)的含义为：
1.若当前节点为左孩子节点，会变成当前节点的双亲节点的右孩子节点。
2.若当前节点为右儿子，会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了，则会变成双亲节点同级的最左边的节点的左孩子节点)
3.该层的每一个节点同时进行一次位移。
4.是从最下面的层开始位移，位移完每一层之后，再向上，直到根节点，位移完毕。
对于数组，左逆右逆全逆。
方法一：对于树，层次遍历，进行数组操作。牛客网判题过程不好，卡常数了。
方法二：下标变换，不需要转。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
root := NewTreeNode(1)
root.left = NewTreeNode(2)
root.right = NewTreeNode(3)
root.left.right = NewTreeNode(4)
root.right.right = NewTreeNode(5)
root.left.right.left = NewTreeNode(3)
root.left.right.right = NewTreeNode(4)
root.right.right.left = NewTreeNode(5)
root.right.right.right = NewTreeNode(6)
printTreeNode(root)
ret := cyclicShiftTree(root, 2)
fmt.Println("--------")
printTreeNode(ret)
}
func printTreeNode(root *TreeNode) {
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
t := queue[0]
fmt.Print(t.val, " ")
queue = queue[1:]
if t.left != nil {
queue = append(queue, t.left)
}
if t.right != nil {
queue = append(queue, t.right)
}
}
fmt.Println("")
}
// 这个类不需要提交
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func NewTreeNode(val int) *TreeNode {
ans := &TreeNode{}
ans.val = val
return ans
}
// 提交下面的代码
//public static TreeNode[] queue = new TreeNode[300000];
var queue = make([]*TreeNode, 300000)
//public static int[] ends = new int[50];
var ends = make([]int, 50)
func cyclicShiftTree(root *TreeNode, k int) *TreeNode {
l := 0
r := 0
queue[r] = root
r++
level := 0
for l != r {
ends[level] = r
for l < ends[level] {
cur := queue[l]
l++
if cur != nil {
queue[r] = cur.left
r++
queue[r] = cur.right
r++
}
}
level++
}
for i := level - 1; i > 0; i-- {
// 当前层 : curLeft....curRight
// 3(null) 4(a) 5(null) 6(b)
// 下一层 ：downLeft....downRight
// 7 8 9 10
// downIndex : 下一层需要根据，k和下一层的长度，来右移。右移之后，从哪个位置开始，分配节点给当前层第一个不空的节点
downLeft := ends[i-1]
downRight := ends[i] - 1
downRightSize := k % (downRight - downLeft + 1)
downIndex := twoSelectOne(downRightSize == 0, downLeft, (downRight - downRightSize + 1))
curLeft := 0
if i-2 >= 0 {
curLeft = ends[i-2]
}
curRight := ends[i-1] - 1
for j := curLeft; j <= curRight; j++ {
if queue[j] != nil {
queue[j].left = queue[downIndex]
downIndex = nextIndex(downIndex, downLeft, downRight)
queue[j].right = queue[downIndex]
downIndex = nextIndex(downIndex, downLeft, downRight)
}
}
}
return root
}
// l......r i -> next index
// 4.....9 i = 7 8 9 4
func nextIndex(i, l, r int) int {
if i == r {
return l
} else {
return i + 1
}
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
