当前位置:网站首页>Leetcode problem solving -- 99 Restore binary search tree
Leetcode problem solving -- 99 Restore binary search tree
2022-07-06 03:07:00 【Snowy solitary boat】
public void recoverTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
TreeNode prev = null;
TreeNode node1=null,node2=null;
while (!stack.isEmpty()||node!=null){
while (node!=null){
stack.push(node);
node = node.left;
}
node = stack.pop();
if (prev!=null&&node.val<prev.val){
if (node1==null){
node1 = prev;
node2 = node;
}else {
node2 = node;
}
}
prev = node;
node = node.right;
}
if (node1!=null&&node2!=null){
int temp = node1.val;
node1.val = node2.val;
node2.val = temp;
}
}
Ideas :
The topic is about switching nodes , In fact, there are only two possibilities , The exchanged nodes are adjacent , Or the exchanged nodes are not adjacent
The exchanged nodes are adjacent :
ai and ai+1 In exchange for , Then there is ai>ai+1 Save two nodes
Can we exchange two nodes directly at this time ? Not at all , Because there is another situation
ai and aj In exchange for , After exchanging
ai>ai+1,aj-1>aj
These two cases are found at the first node , If the situation is the same, we can save the two nodes in the first case , Then, if the next unqualified point appears, it will ai+1 use aj Replace
Then the same switch two nodes at the end of the loop
边栏推荐
- IPv6 jobs
- 解决:AttributeError: ‘str‘ object has no attribute ‘decode‘
- Mysql database operation
- PMP practice once a day | don't get lost in the exam -7.5
- SD卡報錯“error -110 whilst initialising SD card
- 手写数据库客户端
- Zhang Lijun: penetrating uncertainty depends on four "invariants"
- MySQL learning notes-10-tablespace recycling
- Classic interview question [gem pirate]
- How to improve the enthusiasm of consumers when the member points marketing system is operated?
猜你喜欢
A copy can also produce flowers
My C language learning record (blue bridge) -- on the pointer
PMP practice once a day | don't get lost in the exam -7.5
JS regular filtering and adding image prefixes in rich text
【Kubernetes 系列】一文學會Kubernetes Service安全的暴露應用
Mysql database operation
Huawei, H3C, Cisco command comparison, mind map form from the basic, switching, routing three directions [transferred from wechat official account network technology alliance station]
js 正则过滤和增加富文本中图片前缀
IPv6 jobs
MySQL advanced notes
随机推荐
Performance test method of bank core business system
Derivation of anti Park transform and anti Clarke transform formulas for motor control
Classic interview question [gem pirate]
[kubernetes series] learn the exposed application of kubernetes service security
【Kubernetes 系列】一文学会Kubernetes Service安全的暴露应用
tcpdump: no suitable device found
Mysql database operation
Deeply analyze the chain 2+1 mode, and subvert the traditional thinking of selling goods?
CSP date calculation
Function knowledge points
Analyze menu analysis
Pat 1084 broken keyboard (20 points) string find
1003 emergency (25 points), "DIJ deformation"
Reverse repackaging of wechat applet
Modeling specifications: naming conventions
tcpdump: no suitable device found
PMP每日一练 | 考试不迷路-7.5
主数据管理理论与实践
IPv6 jobs
Sign SSL certificate as Ca