검지 Offer: 면접문제 27 - 두 갈래 검색 트리와 양방향 체인 테이블 (java 실현)

문제 설명:
두 갈래 검색 트리를 입력하면 두 갈래 검색 트리를 정렬된 양방향 체인 테이블로 변환합니다.새 결점을 만들 수 없으며 트리에서 결점 포인터의 방향을 조정할 수 있습니다.
아이디어:
나무를 세 부분으로 나눈다. 왼쪽 나무, 뿌리 결점, 오른쪽 나무다.1. 우리는 뿌리 결점과 왼쪽 나무의 최대 결점을 연결해야 한다.뿌리 결점과 오른쪽 나무의 최소 결점을 연결해야 한다.
코드: (책에 적힌 코드대로 했는데 결과가 틀렸어요.) (다음 코드는 남의 코드예요)
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {    
    TreeNode head = null;
    TreeNode realHead = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return realHead;
    }

    private void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return;
        ConvertSub(pRootOfTree.left);
        if (head == null) {
            head = pRootOfTree;
            realHead = pRootOfTree;
        } else {
            head.right = pRootOfTree;
            pRootOfTree.left = head;
            head = pRootOfTree;
        }
        ConvertSub(pRootOfTree.right);
    }
}

좋은 웹페이지 즐겨찾기