当前位置:网站首页>[flax high frequency question] leetcode 426 Convert binary search tree to sorted double linked list
[flax high frequency question] leetcode 426 Convert binary search tree to sorted double linked list
2022-07-03 22:08:00 【Ben potato】
Title Description & link
Leetcode 426 : take BST The structure is transformed into a double linked list structure , Make each node connect its predecessor node and successor node , And head , The last two nodes should also be connected . No extra space required
Topic ideas
I'll give you a compliment on this question , Let me traverse the middle order DFS The template has a deeper understanding . First of all, what if you can open additional space ? Think that there is a hidden property of order traversal in binary trees : In the middle order traversal, the point on the current node is the precursor node , The next point is the successor node . Then you can put BST The structure is traversed in medium order , Save and traverse the array so that each point is connected to the left and right .
What should I do if I don't use extra space . Let's take a look first BST Middle order traversal template , as follows
private void dfs(Node root) {
if(root==null) return;
dfs(root.left);
// The following is the processing area - Displays the current node
System.out.println(root.val);
//
dfs(root.right);
}
We can start processing every time out recursion , Connect the precursor node with the current node , Then connect the head and tail nodes . The whole idea , First, you need to save the header , The last two nodes , First entry in recursion " Processing area " Is the first node , The last entry in recursion " Processing area " It's the last node . How to get the precursor node in recursion , Define a global variable , Save the current node after each processing logic in the processing area , So the next time you enter the processing area , The saved node is the precursor node of this node .
Processing area logic , Connect the current node with the predecessor node , The overall code is as follows :
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node first = null;
Node last = null;
public Node treeToDoublyList(Node root) {
if(root==null) return null;
// The middle order traverses the previous node and the next node
dfs(root);
first.left = last;
last.right = first;
return first;
}
private void dfs(Node root) {
if(root==null) return;
dfs(root.left);
// do something
// The first point entering the processing area must be the first point ( Leftmost point )
if(last!=null) {
// Somewhere in the middle
// The first point is last
last.right = root;
root.left = last;
}
if(first==null) first = root;
last = root; // last Keep updating until the last entry, that is, the rightmost point
dfs(root.right);
}
}
Time complexity :; Spatial complexity :
Recursion depth .
边栏推荐
- 2022-02-15 Daily: 2022 AAAI fellow release
- On my first day at work, this API timeout optimization put me down!
- Decompile and modify the non source exe or DLL with dnspy
- China HDI market production and marketing demand and investment forecast analysis report Ⓢ 2022 ~ 2028
- China's TPMS industry demand forecast and future development trend analysis report Ⓐ 2022 ~ 2028
- Memory analyzer (MAT)
- Why use pycharm to run the use case successfully but cannot exit?
- MySQL - idea connects to MySQL
- QFileDialog
- [dynamic programming] Ji Suan Ke: Suan tou Jun breaks through the barrier (variant of the longest increasing subsequence)
猜你喜欢
Farmersworld farmers world, no faith, how to talk about success?
The latest analysis of R1 quick opening pressure vessel operation in 2022 and the examination question bank of R1 quick opening pressure vessel operation
(5) User login - services and processes - History Du touch date stat CP
No more! Technical team members resign collectively
IPhone development swift foundation 09 assets
Blue Bridge Cup Guoxin Changtian single chip microcomputer -- software environment (II)
treevalue——Master Nested Data Like Tensor
2022 safety officer-a certificate registration examination and summary of safety officer-a certificate examination
MySQL - idea connects to MySQL
Awk getting started to proficient series - awk quick start
随机推荐
Après 90 ans, j'ai démissionné pour démarrer une entreprise et j'ai dit que j'allais détruire la base de données Cloud.
Uboot migration
Global and Chinese market of wireless hard disk 2022-2028: Research Report on technology, participants, trends, market size and share
Implementation principle of inheritance, encapsulation and polymorphism
QFileDialog
Kali2021.4a build PWN environment
Mysql database - Advanced SQL statement (I)
Imitation Netease cloud music applet
Netfilter ARP log
How PHP adds two numbers
treevalue——Master Nested Data Like Tensor
Sed、Awk
[sg function] lightoj Partitioning Game
Persistence of Nacos
2022-02-15 Daily: 2022 AAAI fellow release
Are the top ten securities companies safe to open accounts and register? Is there any risk?
Farmersworld farmers world, no faith, how to talk about success?
[actual combat record] record the whole process of the server being attacked (redis vulnerability)
Station B, dark horse programmer, employee management system, access conflict related (there is an unhandled exception at 0x00007ff633a4c54d (in employee management system.Exe): 0xc0000005: read locat
Under the double reduction policy, research travel may become a big winner