recover-binary-search-tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n ) space is pretty straight forward. Could you devise a constant space solution?
confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".
2. 사고: 이 진 트 리 에 오류 가 발생 했 는 지, 중간 순서 로 옮 겨 다 니 는 이전 요소 가 현재 요소 보다 작 았 는 지 검색 합 니 다.모두 다음 두 가지 상황 으로 나 뉜 다.
public class RecoverSearchTree {
public static void main(String[] args) {
TreeNode root =new TreeNode(0);
root.left = new TreeNode(1);
RecoverSearchTree test = new RecoverSearchTree();
test.recoverTree(root);
}
private TreeNode firstErrorNode = null;
private TreeNode secondErrorNode = null;
private TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = firstErrorNode.val;
firstErrorNode.val = secondErrorNode.val;
secondErrorNode.val = temp;
}
private void inOrder(TreeNode root) {
if(root == null)
return;
inOrder(root.left);
if(preNode.val >= root.val ){
if(firstErrorNode == null){
firstErrorNode = preNode;
secondErrorNode = root;
}else{
secondErrorNode = root;
}
}
//
// , preNode root
// root
preNode = root;
inOrder(root.right);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.