博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Recover Binary Search Tree@LeetCode
阅读量:5971 次
发布时间:2019-06-19

本文共 1153 字,大约阅读时间需要 3 分钟。

根据BST树的特性来,对BST的中序遍历,得到的是一个升序数列。所以在遍历过程中检测出两个异常的位置,对其进行交换即可。

一旦有两个位置的节点被交换了,那么中序遍历就会出现有两个:Node[i] > Node[i + 1]其中i是错误位置,Node[j] < Node[j - 1]其中j是错误位置,遵循这个规律,找到相应的Node[i]Node[j]对其进行交换(只交换val值)即可。

实现代码如下:

javapublic class Solution {    private TreeNode wrongLessNode;    private TreeNode wrongLargerNode;    private TreeNode preNode;    public void recoverTree(TreeNode root) {        recover(root);        if (wrongLessNode != null && wrongLargerNode != null) {            int temp = wrongLessNode.val;            wrongLessNode.val = wrongLargerNode.val;            wrongLargerNode.val = temp;        }    }    private void recover(TreeNode root) {        if (root == null)            return;        if (preNode == null && root.left == null) {            preNode = root;        }        recover(root.left);        if (preNode != null && root.val < preNode.val) {            if (wrongLessNode == null) {                wrongLessNode = preNode;                wrongLargerNode = root;            }            else {                wrongLargerNode = root;                return;            }        }        preNode = root;        recover(root.right);    }}

转载地址:http://bpzox.baihongyu.com/

你可能感兴趣的文章
LDAP&it's usage
查看>>
模式和原则[转载]
查看>>
[Codeforces958F2]Lightsabers (medium)(思维)
查看>>
获取非行间样式
查看>>
java String format占位符
查看>>
JAVA spring配置文件总结
查看>>
Java5的 线程并发库
查看>>
HDOJ 1036 输入输出 水
查看>>
Java 安装后的检测是否安装成功
查看>>
Google Map API使用详解(七)——加载Google Map API URL的详细解读
查看>>
设备及分辨率
查看>>
mybatis拦截器
查看>>
Simple But Useful Samples About 'grep' Command(简单实用的grep 命令)
查看>>
ecshop分类页调用分类名称
查看>>
安全的文件访问方式
查看>>
揭秘PPT设计中的逻辑真相
查看>>
[转载]ACM搜索算法总结(总结)
查看>>
【大数据系列】hadoop命令指导官方文档翻译
查看>>
VS添加服务引用和 Web引用的区别
查看>>
漫谈可视化Prefuse(四)---被玩坏的Prefuse API
查看>>