【牛客算法】某司面试算法题:循环右移二叉树

news/2024/10/31 17:18:32/

一、算法题描述

1.1 算法描述

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

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

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

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

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

如果从最后一层开始对该二叉树的每一层循环位移k位。以下方二叉树为例,k=1:

			 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 算法思路

  1. 层序遍历:使用队列进行BFS(层次遍历),同时记录每个节点在每一层的位置信息,包括父节点位置、当前节点位置以及是否为左孩子或右孩子。将这些信息存储在levels数组中,每个元素是一个列表,包含该层所有节点的信息。

  2. 位移操作:从最底层开始,逐层向上进行位移操作。对于每一层,首先计算出这一层需要位移的步数,然后根据位移步数调整每个节点的左右子节点指针。

  3. 指针重构:在位移过程中,需要重新构建每个节点的左右子节点指针。这可以通过遍历levels数组中的每层节点,并根据它们的父节点位置和位移步数来确定新的子节点位置。

  4. 更新指针:在位移操作完成后,需要更新上一层的节点指针,将当前层的节点连接到上一层的相应节点上。

  5. 处理边界条件:在位移过程中,需要注意处理边界条件,例如当位移步数超过当前层节点数时,需要对步数进行取模操作。

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;  // 空树处理// 存储每层的节点信息,用于后续循环位移和指针重构ArrayList<ArrayList<Node>> levels = new ArrayList<>();Queue<Node> queue = new LinkedList<>();// 初始化:根节点加入队列queue.offer(new Node(0, 0, 0, root));// `parentNum`记录当前层节点数,`nextNum`记录下一层节点数int parentNum = 1, nextNum = 0;ArrayList<Node> 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) {  // 从最底层向上逐层处理ArrayList<Node> 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 算法复杂度分析

  1. 时间复杂度算法的时间复杂度主要取决于树的节点数n以及位移步数k。在最坏情况下,我们需要对每个节点进行位移操作,因此时间复杂度为O(n * k)。然而,由于位移操作的步数k通常远小于树的节点数n,因此实际的时间复杂度通常接近O(n)。

  2. 空间复杂度算法的空间复杂度主要取决于树的高度h和每层的节点数。在最坏情况下,我们可能需要存储所有层的节点信息,因此空间复杂度为O(n),其中n为树的节点数。


http://www.ppmy.cn/news/1543395.html

相关文章

2024年三个月自学网络安全(黑客技术)学习指南。

&#x1f91f; 基于入门网络安全/黑客打造的&#xff1a;&#x1f449;黑客&网络安全入门&进阶学习资源包 前言 什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、…

Django入门教程——数据模型建立

第二章&#xff1a;数据模型建立 教学目的 了解模板引擎的创建理解模板引擎的基本语法了解系统设计的基本原则&#xff0c;重点理解数据库的设计。了解ORM概念&#xff0c;理解数据模型创建方法。 模板引擎设置 Django的核心组件包括&#xff1a; 模型&#xff08;Model&a…

vue + elementui 全局Loading效果

注&#xff1a;在request请求和响应封装的文件里引入loading&#xff0c;发请求时打开loading&#xff0c;响应时关闭loading&#xff0c;这样每个接口调用时都会有loading效果 &#xff08;1&#xff09; 首先确保项目中安装了element-ui这个依赖包 npm i element-ui -S&…

阿里云物联网的通信方式

阿里云物联网通信的两种方式&#xff0c;一个是物模型&#xff08;分为服务&#xff0c;事件&#xff0c;属性此篇文章只讲解物模型中的服务和属性用法&#xff09;&#xff0c;一个是自定义topic&#xff08;要另外设置数据流转&#xff09; 1.使用产品内的功能定义&#xff0…

hivesql学习大纲

引言 - 简述Hive的用途和特点 - 为什么学习HiveSQL 第一部分&#xff1a;Hive基础 1.1 Hive简介 - 定义和架构 - Hive与传统数据库的区别 - Hive的应用场景 1.2 Hive环境搭建 - 所需环境和依赖 - 安装和配置Hive - 启动和停止Hive服务 1.3 Hive数据模型 - 数据库&#xff0…

关于synchronized死锁问题

大家先猜一下下面这个代码是否可以成功运行&#xff1f; Thread t new Thread(() - >{ synchronized(locker){ synchronized(locker){ //..随便写点啥都行 System.out.println("hello");}} }); t.start(); 从直观上感觉&#xff0c;这个加锁应该是不能成功呀!…

Django-中间件

定义&#xff1a; 编写中间件&#xff1a; 注册中间件&#xff1a; 添加中间件&#xff1a; 1.在项目目录下添加一个文件夹&#xff08;名字随意&#xff09;&#xff0c;然后文件夹下创建.py文件 2.将中间件添加到setting文件中 MIDDLEWARE [django.middleware.security.Se…

2024年【北京市安全员-A证】考试题及北京市安全员-A证复审考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 北京市安全员-A证考试题是安全生产模拟考试一点通总题库中生成的一套北京市安全员-A证复审考试&#xff0c;安全生产模拟考试一点通上北京市安全员-A证作业手机同步练习。2024年【北京市安全员-A证】考试题及北京市安…