Recover Binary Search Tree -- LeetCode

원본 링크:  http://oj.leetcode.com/problems/recover-binary-search-tree/
 
이 문 제 는 두 개의 요소 가 잘못 바 뀐 이 진 트 리 를 복원 하 라 는 것 이다.처음에는 복잡 하 게 느 낄 수 있 지만 규칙 을 살 펴 보면 간단 하 다.주로 이 진 지 를 이용 하여 나무의 주요 성질 을 찾 는 것 이 바로 중간 순서 가 질서 있 는 성질 이다.그러면 그 중에서 요소 가 바 뀌 면 중간 순서 가 반복 되 는 과정 에서 질서 에 어 긋 나 는 상황 이 반드시 발생 한 다 는 것 을 의미한다.그러면 몇 번 나 올 까요?두 가지 상황 이 있 습 니 다.만약 에 중간 순서 가 서로 인접 한 두 요소 가 바 뀌 었 다 면 한 번 의 위반 상황 이 발생 할 것 이 라 고 생각 하기 쉽 습 니 다.이 두 노드 를 기록 하고 마지막 으로 값 을 바 꾸 면 됩 니 다.만약 에 서로 인접 하지 않 은 두 요소 가 바 뀌 었 다 면 예 를 들 어 두 번 의 역순 이 발생 할 수 있다 는 것 을 쉽게 알 수 있다.그러면 이때 바 꿔 야 할 요 소 는 첫 번 째 역순 앞의 요소 와 두 번 째 역순 뒤의 요소 여야 한다.예 를 들 어 1234567,1 과 5 를 바 꾸 면 5234167 을 얻 을 수 있 고 역순 은 52 와 41 에서 발생 한다.우 리 는 4 와 1 을 바 꿔 야 한다.그러면 52 의 첫 번 째 요소,41 의 두 번 째 요 소 를 바 꾸 면 된다.
규칙 을 알 면 쉽게 이 루어 진다.중 서 는 역순 상황 을 찾 아 다 니 며 바 꾸 는 첫 번 째 요 소 는 영원히 첫 번 째 역순 의 첫 번 째 요소 이 고 바 꾸 는 두 번 째 요 소 는 한 번 의 역순 이 라면 그 다음 이 고 두 번 의 역순 이 있 으 면 두 번 째 다음 이다.알고리즘 은 한 번 의 중간 순서 로 옮 겨 다 니 기 때문에 시간 복잡 도 는 O(n)이 고 공간 은 스 택 크기 O(logn)입 니 다.코드 는 다음 과 같 습 니 다: 

public void recoverTree(TreeNode root) {
    if(root == null)
        return;
    ArrayList<TreeNode> pre = new ArrayList<TreeNode>();
    pre.add(null);
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    helper(root,pre, res);
    if(res.size()>0)
    {
        int temp = res.get(0).val;
        res.get(0).val = res.get(1).val;
        res.get(1).val = temp;
    }
}
private void helper(TreeNode root, ArrayList<TreeNode> pre, ArrayList<TreeNode> res)
{
    if(root == null)
    {
        return;
    }
    helper(root.left, pre, res);
    if(pre.get(0)!=null && pre.get(0).val>root.val)
    {
        if(res.size()==0)
        {
            res.add(pre.get(0));
            res.add(root);
        }
        else
        {
            res.set(1,root);
        }
    }
    pre.set(0,root);
    helper(root.right,pre,res);
}

이 를 통 해 알 수 있 듯 이 pre 는 하나의 Array List 로 저장 되 어 있 습 니 다.이렇게 하 는 이 유 는 자바 가 모두 값 전달 이기 때문에 우 리 는 pre 의 값(현재 함수 가 아 닌)을 전체적으로 변화 시 켜 야 합 니 다.한 배열 만 전달 할 수 있 고 결점 의 주 소 를 바 꿀 수 있 습 니 다.이 점 은 매우 중요 합 니 다.자바 와 C+가 비교적 큰 차이 점 입 니 다.모 르 는 친 구 는 연구 해 보 세 요.
이 문 제 는 이 진 트 리 를 살 펴 보 는 것 이지 만 응용 문 제 는 서로 다른 껍질 을 씌 워 야 한다.우 리 는 이 진 트 리 의 성질 을 이용 하여 규칙 을 관찰 한 후에 야 풀 수 있다.