Leetcode99 恢复二叉搜索树

题目地址:
https://leetcode-cn.com/problems/recover-binary-search-tree/

【思路】
在一次遍历的过程中,找到两个异常的节点,把这两个节点的值交换。
怎么找呢?
二叉搜索树的中序遍历是一个升序数组
可记录每一次遍历的前置节点
遍历到的节点的value一定要比前置节点的大
如果比前置节点要小 则记录为异常

上代码

class Solution {
public:
    TreeNode* x = nullptr;
    TreeNode* y = nullptr;
    TreeNode* preValue = nullptr;
    void inOrder(TreeNode* node){
        if(node == nullptr) return;
        inOrder(node -> left);
        if(preValue != nullptr){
            if(node -> val < preValue -> val){
                y = node;
                if(x == nullptr) x = preValue;
                else return;
//记录节点的小技巧
            }
        }
        preValue = node;
        inOrder(node ->right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int tmp = x->val;
        x->val = y->val;
        y->val = tmp;
    }

};

【记录节点的小技巧】
有两种交换情况:
相邻的两个节点交换了,不相邻的两个节点交换了


image.png

相邻交换记录异常的两个就行了
不相邻交换时,异常的preValue才是出问题的那个
(自己想一想)

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容