2022-03-21：循环右移二叉树。

原创

福大大架构师每日一题

发布于 2022-03-21 21:23:35

4600

发布于 2022-03-21 21:23:35

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-03-21：循环右移二叉树。

现有一棵个节点构成的二叉树，请你将每一层的节点向右循环位移位。某层向右位移一位(即)的含义为：

1.若当前节点为左孩子节点，会变成当前节点的双亲节点的右孩子节点。

2.若当前节点为右儿子，会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了，则会变成双亲节点同级的最左边的节点的左孩子节点)

3.该层的每一个节点同时进行一次位移。

4.是从最下面的层开始位移，位移完每一层之后，再向上，直到根节点，位移完毕。

腾讯音乐2022校园招聘。

答案2022-03-21：

对于数组，左逆右逆全逆。

方法一：对于树，层次遍历，进行数组操作。牛客网判题过程不好，卡常数了。

方法二：下标变换，不需要转。

代码用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
	}
}

执行结果如下：