Leetcode: 99. Recover Binary Search Tree | 含C++笔记

binary search tree中，本来遵守着从中间Node切开，左边小於右边的规则，但是现在有其中两个Node错置了。

资料错误要怎麽修正？

从来没做过。

思路

要找到不符合规则的点，第一直觉是，判断这棵树是不是BST，但除此之外没有任何想法。

吸收知识时间

晃一晃脑子，看能不能把知识晃出来，啊结果只有水...

忘了一件事，二元树的结构的其中一个性质：可以用一维阵列储存，然後用index去存取特定节点，像是：index从1开始的话，1是root，每个节点index=i，则左小孩index=2*i，右小孩index=2*i+1，而自己的index/2则是父的节点index。

这样的话，一维阵列很好处理啊，只要sort，再放值回去就好。

但是

啊哈，但是题目给的二元树，是用struct建立起来的呢！

实在没想法。

C++笔记

// first为 准备指向型态为TreeNode 的指标，现在还没指向任何TreeNode
TreeNode* first = NULL; 

//cout << first; // stdout: 0
//cout << first->val; // error

//新增一个TreeNode变数，同时赋最小Int常数给val。并将此新TreeNode交给指标prev指着。
TreeNode* prev = new TreeNode(INT_MIN); 

//cout << prev->val; //stdout: -2147483648

程序码

class Solution {
public:
    TreeNode* first = NULL;
    TreeNode* second = NULL;
    TreeNode* prev = new TreeNode(INT_MIN);
    
    void inorder(TreeNode* curr) {
        if (curr == NULL)
            return;
        inorder(curr->left);
        if (first == NULL && prev->val > curr->val)
            first = prev;
        if (first != NULL && prev->val > curr->val)
            second = curr;
        prev = curr;
        inorder(curr->right);
    }    
    
    void recoverTree(TreeNode* root) {
        inorder(root);
        int temp = second->val;
        second->val = first->val;
        first->val = temp;
    }
};

参考：
https://www.cnblogs.com/grandyang/p/4298069.html

https://leetcode.com/problems/recover-binary-search-tree/discuss/1499780/C%2B%2B%3A-simple-and-intuitive