LeetCode99 恢复二叉搜索树

发表于 | 分类于 |
字数统计: 346 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/recover-binary-search-tree

题意

给定一个二叉查找树，已知有两个节点被不小心交换了，试复原此树。

解法

利用二叉查找树的中序遍历有序性
找到不符合条件的节点进行交换
每次记录prev节点
这里一开始写的时候陷入了一个困境
即如何记录prev节点 想的时候想错了
误把遍历时候访问的节点当成了prev节点
最后使用全局变量的方式 每次中序遍历访问的节点

出现顺序不符的情况有两种，一种是遍历整个过程出现一次次序错误，还有一种是两次次序错误
如果一次，则说明这两个节点需要交换
如果两次，则交换这两个节点
要注意交换的这两个节点分别是第一个的prev和第二个root（这里一开始也卡住了）
细节见代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<TreeNode*> vt;
    TreeNode* prev;
    void inOrder(TreeNode* root) {
        if(!root) return;
        inOrder(root -> left);
        if(prev) {
            if (prev -> val > root -> val) {
                if (vt.empty()) {                   
                    vt.push_back(prev);
                    vt.push_back(root);
                }
                else {
                    vt.pop_back();
                    vt.push_back(root);
                }
            }
        }
        prev = root;
        inOrder(root -> right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int val = vt[0] -> val;
        vt[0] -> val = vt[1] -> val;
        vt[1] -> val = val;
    }
};