426. Convert Binary Search Tree to Sorted Doubly Linked List
2022/2/5 6:12:31
本文主要是介绍426. Convert Binary Search Tree to Sorted Doubly Linked List,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
This is a "In Order" traversal problem, because the order of the result is a in order or the tree.
1. The problem need to return the pointer to the smallest element of the linked list, so we first need to find the smallest element.
2. The problem requires "We want to do the transformation in place", that mean we should not create a new link.
3. We need a "pre-node" to indicate the last node that was just traversed before the current node.
The solution is as following, time complexity is O(n):
private Node pre = new Node(); //3. pre-node public Node treeToDoublyList(Node root) { if(root==null) return null; Node head = root; while(head.left!=null){ head = head.left; //1. find the smallest element } inOrder(root); pre.right = head; head.left = pre; return head; } private void inOrder(Node root){ //2. in place if(root == null) return; inOrder(root.left); pre.right = root; root.left = pre; pre = root; inOrder(root.right); }
这篇关于426. Convert Binary Search Tree to Sorted Doubly Linked List的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享