LC99: Recover Binary Search Tree

작성일

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

  • 평볌한 dfs 문제이다. In-Order 로 정렬하고 해당 뒤틀어진 부분을 찾아서 교환해주면 끝
  • 하드라고 보기는 어렵다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	TreeNode *prev = nullptr;
    TreeNode *left = nullptr, *right = nullptr;
    int done = 0;
public:
	void dfs(TreeNode* cur) {
		if(!cur || done == 2) return;
		dfs(cur->left);
        if (prev && prev->val > cur->val) {
            if(!left) left = prev;
            right = cur;
            done++;
        }
        prev = cur;
		dfs(cur->right);
	}
    void recoverTree(TreeNode* root) {
    	dfs(root);
        swap(left->val, right->val);
    }
};