이웃한 부모자식 간의 관계만 조사해서는
전체 이진트리의 타당성이 증명되지 않는다는 것을
무식하게 깨닫고 leaf부터 조사해야겠다고 느꼈습니다.
(leaf까지 거쳐야하는 노드들을 keep하면서요..!)
각 leaf들에 대해 루트까지 올라가면서
타당성을 조사했을때
( ex. 13은 14보다 왼쪽에있고, 10보다 오른쪽에 있고, 마지막으로 루트인 8보다 오른쪽에 있으니 타당)
결국 leaf기준 depth에서 depth+1 도 타당해야하고,
depth+1 이 타당하려면 depth+2도 타당해야하고 ...
이런식으로 귀납적인 증명을 하면 충분한 걸까요?
필요충분하지 않다면
다른 어떤 증명이 필요할까요?
이런 생각이 옳지않다면
뭘 놓치고 있는지 지적해주시면 감사하겠습니다.
depth n+1의 한 node를 root로 하는 subtree들이 BST라는 게 depth n의 한 node를 root로 하는 subtree들이 BST라는 것의 충분조건인지 필요조건인지 체크해보세요
+ 임의의 tree에서 leaf node를 root로 하는 subtree가 BST가 아닌 경우가 있는지 체크해보세요
알겠습니다..
타당하다는게 뭔말임? 그런용어 처음 듣는데
valid
타당타당 하는 의성어 생각한건 아니지...? ㅋㅋㅋㅋ
root에서부터 조건을 interval로 가져가면 됨
3을 검사할 때 (-inf, 8), 6을 검사할 때 (3,8), 4를 검사할 때 (3,6) 이런 식으로