当前位置:网站首页>[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 .
边栏推荐
- Morning flowers and evening flowers
- 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.
- What indicators should be paid attention to in current limit monitoring?
- China HDI market production and marketing demand and investment forecast analysis report Ⓢ 2022 ~ 2028
- js demo 计算本年度还剩下多少天
- What if the Flink SQL client exits and the table is emptied?
- Preliminary analysis of smart microwave radar module
- Go language slice interview real question 7 consecutive questions
- 鹏城杯 WEB_WP
- QGIS grid processing DEM data reclassification
猜你喜欢
Redis concludes that the second pipeline publishes / subscribes to bloom filter redis as a database and caches RDB AOF redis configuration files
Blue Bridge Cup Guoxin Changtian single chip microcomputer -- led lamp module (V)
2022 free examination questions for safety management personnel of hazardous chemical business units and reexamination examination for safety management personnel of hazardous chemical business units
How PHP gets all method names of objects
Awk getting started to proficient series - awk quick start
gslb(global server load balance)技术的一点理解
2022 safety officer-a certificate registration examination and summary of safety officer-a certificate examination
Preliminary analysis of smart microwave radar module
Exclusive interview with the person in charge of openkruise: to what extent has cloud native application automation developed now?
Implementation principle of inheritance, encapsulation and polymorphism
随机推荐
China's TPMS industry demand forecast and future development trend analysis report Ⓐ 2022 ~ 2028
Exness: the Central Bank of England will raise interest rates again in March, and inflation is coming
[SRS] build a specified version of SRS
Common SQL sets
Blue Bridge Cup Guoxin Changtian single chip microcomputer -- software environment (II)
Tkinter Huarong Road 4x4 tutorial III
Farmersworld farmers world, no faith, how to talk about success?
How does sentinel, a traffic management artifact, make it easy for business parties to access?
DR882-Qualcomm-Atheros-QCA9882-2T2R-MIMO-802.11ac-Mini-PCIe-Wi-Fi-Module-5G-high-power
Cognitive fallacy: what is dimensional curse
Leetcode problem solving - 235 Nearest common ancestor of binary search tree
Blue Bridge Cup Guoxin Changtian MCU -- program download (III)
QFileDialog
What should the future of the Internet be like when Silicon Valley employees flee the big factory and rush to Web3| Footprint Analytics
How to obtain opensea data through opensea JS
Getting started with DOM
Capturing and sorting out external articles -- autoresponder, composer, statistics [III]
How to store null value on the disk of yyds dry inventory?
Idea shortcut word operation
Development trend and market demand analysis report of China's energy storage battery industry Ⓩ 2022 ~ 2028