검지 Offer: 면접문제 27 - 두 갈래 검색 트리와 양방향 체인 테이블 (java 실현)
1710 단어 주제와 경험을 고쳐 쓰다
두 갈래 검색 트리를 입력하면 두 갈래 검색 트리를 정렬된 양방향 체인 테이블로 변환합니다.새 결점을 만들 수 없으며 트리에서 결점 포인터의 방향을 조정할 수 있습니다.
아이디어:
나무를 세 부분으로 나눈다. 왼쪽 나무, 뿌리 결점, 오른쪽 나무다.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);
}
}