[LeetCode] 99. Recover Binary Search Tree(复原BST) ☆☆☆☆☆
2024-10-18 14:05:14
Recover Binary Search Tree leetcode java
描述
解析
解决方法是利用中序遍历找顺序不对的两个点,最后swap一下就好。
因为这中间的错误是两个点进行了交换,所以就是大的跑前面来了,小的跑后面去了。
所以在中序遍利时,遇见的第一个顺序为递减的两个node,大的那个肯定就是要被recovery的其中之一,要记录。
另外一个,要遍历完整棵树,记录最后一个逆序的node。
简单而言,第一个逆序点要记录,最后一个逆序点要记录,最后swap一下。
因为Inorder用了递归来解决,所以为了能存储这两个逆序点,这里用了全局变量,用其他引用型遍历解决也可以。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode pre;
TreeNode first;
TreeNode second; public void inorder(TreeNode root){
if(root == null)
return; inorder(root.left);
if (pre == null) {
pre = root; //pre指针初始
} else {
if (pre.val > root.val) {
if(first == null) {
first = pre;//第一个逆序点
}
second = root; //不断寻找最后一个逆序点
}
pre = root; //pre指针每次后移一位
}
inorder(root.right);
} public void recoverTree(TreeNode root) {
pre = null;
first = null;
second = null;
inorder(root);
if (first != null && second != null) {
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
}
最新文章
- POJ 2352 Stars 线段树
- jboss hello world
- 处理OSX创建的U盘, 删除EFI分区
- Android成长日记-LogCat
- php 实现推技术comet(转)
- vs2010 问题 LINK : fatal error LNK1123: 转换到 COFF 期间失败: 文件无效或损坏
- poj1927Area in Triangle
- Unit4中的Annotation
- 【问题汇总】ListView的FooterView设置可见性的问题
- BZOJ1603: [Usaco2008 Oct]打谷机
- [HNOI 2013] 消毒 (搜索,二分图匹配)
- JAVA大整数傻瓜入门
- WCF技术剖析之三:如何进行基于非HTTP的IIS服务寄宿
- POJ 2318 TOYS(计算几何)
- BTrace : Java 线上问题排查神器
- centos7下安装Go环境
- Hadoop的namenode的管理机制,工作机制和datanode的工作原理
- 小程序html转wxml,微信小程序用wxParse解析html
- 使用log4net将C#日志发送到Elasticsearch
- c# 调试模式下Swaggerf附加接口参数
热门文章
- Http_code码
- Python 一个抓取糗百的段子的小程序
- python测试框架&;&;数据生成&;&;工具最全资源汇总
- win10常用命令和设置总结
- IIS上部署MVC网站,打开后ExtensionlessUrlHandler-4.0
- ts问题处理(2): 'Promise' only refers to a type, but is being used as a value here.
- 《剑指offer》第五十六题(数组中只出现一次的两个数字)
- 《剑指offer》第五十题(字符流中第一个只出现一次的字符)
- vue.js环境配置步骤及npm run dev报错解决方案
- new int