在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
此题为July在CSDN发布的微软编程面试100题中的第一题,觉得蛮有趣的,今天也拿过来玩玩,July的代码用的是C++实现,可能因为有指针的原因吧,感觉看起来相对比较容易理解整个的实现过程,而我,试着用C#完成这样的功能。 完整的题目如下: 把二元查找树转变成排序的双向链表,要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 转换成双链表 4=6=8=10=12=14=16 动手编码之前,先回顾下二叉查找树的特点:任意节点的左子树都要小于当前节点,右子树都要大于当前节点。查询某个值,需要的时间复杂度为O(lgN)。 现在要求将其由树状结构改造成线性结构的双向链表,重点在于,获得当前节点左子树范围内最右节点(也是左子树最大值节点),以及右子树范围内最左节点(也是右子树最小值节点),然后,调整这两个节点当前节点左右顺序。即调整8、10之间和12、10之间的关系。 算法思路:
C#源码部分: 首先定义根节点和左右子树节点: private int value; private MyLinkedNode left; private MyLinkedNode right; public MyLinkedNode(int value) { this.value = value; } public MyLinkedNode Left { get { return this.left; } set { this.left = value; } } public MyLinkedNode Right { get { return this.right; } set { this.right = value; } } 以下代码为逻辑递归代码: private static void ProcessTreeToLinked(MyLinkedNode node) { if (null==node) { return; } //获取左子树的最右节点 MyLinkedNode leftR = getMostRightNode(node.Left); //获取右子树的最左节点 MyLinkedNode rightL = getMostLeftNode(node.Right); //左子树非空,递归处理左子树 if (null == node.Left) { ProcessLeftNode(node.Left, node); } //若右子树非空,递归处理右子树 if (null == node.Right) { ProcessRightNode(node.right, node); } //若左子树最右节点非空,调整与根节点相邻 if (null != leftR) { leftR.Right = node; node.Left = leftR; } //若右子树的最左节点非空,调整与根节点相邻 if (null != rightL) { rightL.Left = node; node.Right = rightL; } } private static void ProcessRightNode(MyLinkedNode right, MyLinkedNode node) { //若右子树为叶子节点,直接将其左向索引指向父节点,并返回 if (isLeafNode(right)) { right.Left = node; return; } ProcessTreeToLinked(right); } private static void ProcessLeftNode(MyLinkedNode left, MyLinkedNode node) { //若左子树为叶子节点,直接将其右向索引指向父节点,并返回 if (isLeafNode(left)) { left.Right = node; return; } //本节点当作根节点,递归调用 ProcessTreeToLinked(left); } private static bool isLeafNode(MyLinkedNode node) { return (null == node.Left) && (null == node.Right); } private static MyLinkedNode getMostLeftNode(MyLinkedNode right) { if (null == right) { return null; } if (null == right.Left) { return right; } return getMostLeftNode(right.Left); } private static MyLinkedNode getMostRightNode(MyLinkedNode left) { if (null==left) { return null; } if (null==left.Right) { return left; } return getMostRightNode(left.Right); }
编写这段代码其实不难,难的是如何理清楚解题思路。权当为接下来的面试做准备了,上次面试被问到要实现String.Replace()方法,却不能调用API,不得不说,作为一名测试人员,这样的编码难度对我来说还是比较大的,但并非不可克服,只是,需要继续努力提升自己~轻轻地,对自己说一声,加油~ |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论