设计找图网站,免费建站的方法,seo优化心得,快速排名优化推广手机一、算法题描述
1.1 算法描述
现有一棵n个节点构成的二叉树#xff0c;请你将每一层的节点向右循环位移k位。某层向右位移一位(即k1)的含义为#xff1a; 若当前节点为左孩子节点#xff0c;会变成当前节点的双亲节点的右孩子节点。 若当前节点为右儿子#xff0c;会变成…一、算法题描述
1.1 算法描述
现有一棵n个节点构成的二叉树请你将每一层的节点向右循环位移k位。某层向右位移一位(即k1)的含义为 若当前节点为左孩子节点会变成当前节点的双亲节点的右孩子节点。 若当前节点为右儿子会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了则会变成双亲节点同级的最左边的节点的左孩子节点) 该层的每一个节点同时进行一次位移。 是从最下面的层开始位移位移完每一层之后再向上直到根节点位移完毕。
如果从最后一层开始对该二叉树的每一层循环位移k位。以下方二叉树为例k1 1/ \2 3/ \4 5位移最后一层5变成2的左孩子节点4变成3的右孩子节点如下图: 1/ \2 3/ \5 4再位移倒数第二层3变成1的左孩子节点2变成1的右孩子的节点它们的孩子节点随着一起位移如下图 1/ \3 2\ /4 5根节点没有双亲节点不用位移位移完毕
现在给你这棵二叉树请你返回循环右移k位后的二叉树。
1.2 示例
1.2.1 示例1
输入
{1,2,3,#,#,4,5},1输出
{1,3,2,#,4,5}说明
解释见题面描述。 1.2.1 示例2
输入
{1,2,3,4},2输出
{1,2,3,#,#,4}说明 1/ \2 3/4变为1/ \2 3/4
1.2.3 示例3
输入
{1,#,3,4,5},1输出
{1,3,#,5,4}说明 1\3/ \4 5变为1\3/ \5 4变为1/3/ \5 4
1.4 备注
树的节点个数在[1,10^5]之间且保证该树上每个节点的编号不同节点编号并非按顺序排列1≤k≤100。
1.5 提供的代码
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param root TreeNode类 * param k int整型 * return TreeNode类*/public TreeNode cyclicShiftTree (TreeNode root, int k) {// write code here}
}二、算法实现
2.1 算法思路 层序遍历使用队列进行BFS层次遍历同时记录每个节点在每一层的位置信息包括父节点位置、当前节点位置以及是否为左孩子或右孩子。将这些信息存储在levels数组中每个元素是一个列表包含该层所有节点的信息。 位移操作从最底层开始逐层向上进行位移操作。对于每一层首先计算出这一层需要位移的步数然后根据位移步数调整每个节点的左右子节点指针。 指针重构在位移过程中需要重新构建每个节点的左右子节点指针。这可以通过遍历levels数组中的每层节点并根据它们的父节点位置和位移步数来确定新的子节点位置。 更新指针在位移操作完成后需要更新上一层的节点指针将当前层的节点连接到上一层的相应节点上。 处理边界条件在位移过程中需要注意处理边界条件例如当位移步数超过当前层节点数时需要对步数进行取模操作。
2.2 算法实现
import java.util.*;/** TreeNode类定义* public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {// Node类封装了节点的层次信息便于后续重构指针class Node {int parentIndex; // 父节点在当前层的位置int currentIndex; // 当前节点在该层的索引位置int flag; // 标记当前节点是左孩子(0)还是右孩子(1)TreeNode currentNode; // 当前节点的引用// 构造方法public Node(int parentIndex, int currentIndex, int flag, TreeNode currentNode) {this.parentIndex parentIndex;this.currentIndex currentIndex;this.flag flag;this.currentNode currentNode;}}public TreeNode cyclicShiftTree(TreeNode root, int k) {if (root null) return null; // 空树处理// 存储每层的节点信息用于后续循环位移和指针重构ArrayListArrayListNode levels new ArrayList();QueueNode queue new LinkedList();// 初始化根节点加入队列queue.offer(new Node(0, 0, 0, root));// parentNum记录当前层节点数nextNum记录下一层节点数int parentNum 1, nextNum 0;ArrayListNode tempLevel new ArrayList(); // 当前层的节点列表// 层次遍历记录每层节点的结构信息while (!queue.isEmpty()) {Node node queue.poll();tempLevel.add(node); // 将节点加入当前层的列表--parentNum;// 添加左子节点到队列if (node.currentNode.left ! null) {queue.offer(new Node(node.currentIndex, nextNum, 0, node.currentNode.left));}// 添加右子节点到队列if (node.currentNode.right ! null) {queue.offer(new Node(node.currentIndex, nextNum, 1, node.currentNode.right));}// 当前层遍历完毕将其加入到levels并更新下一层if (parentNum 0) {parentNum nextNum;nextNum 0;levels.add(tempLevel);tempLevel new ArrayList();}}// 从树的最底层开始逐层循环右移并更新左右子节点指针int depth levels.size() - 1;for (int i depth; i 1; --i) { // 从最底层向上逐层处理ArrayListNode parentLevel levels.get(i - 1);int parentLevelSize parentLevel.size();// 清空上一层每个节点的左右子节点准备重新分配指针for (Node parent : parentLevel) {parent.currentNode.left null;parent.currentNode.right null;}// 计算当前层的位移步数int move k % (2 * parentLevelSize); // 控制位移在有效范围内tempLevel levels.get(i);// 根据位移更新每个节点的左右子节点指针for (Node node : tempLevel) {// 计算目标父节点位置和孩子标记左孩子或右孩子int targetParentIndex node.flag 0? (node.parentIndex move / 2) % parentLevelSize: (node.parentIndex (move 1) / 2) % parentLevelSize;int targetChildFlag node.flag 0 ? move % 2 : (move 1) % 2;// 获取目标父节点Node targetParent parentLevel.get(targetParentIndex);// 根据targetChildFlag更新子节点指针if (targetChildFlag 0) {targetParent.currentNode.left node.currentNode;} else {targetParent.currentNode.right node.currentNode;}}}return root; // 返回根节点树的结构已完成位移并更新}
}
2.3 算法复杂度分析 时间复杂度算法的时间复杂度主要取决于树的节点数n以及位移步数k。在最坏情况下我们需要对每个节点进行位移操作因此时间复杂度为O(n * k)。然而由于位移操作的步数k通常远小于树的节点数n因此实际的时间复杂度通常接近O(n)。 空间复杂度算法的空间复杂度主要取决于树的高度h和每层的节点数。在最坏情况下我们可能需要存储所有层的节点信息因此空间复杂度为O(n)其中n为树的节点数。
