홈>
0 만 포함하는 모든 하위 트리를 제거하려고합니다. 내 코드는 다음과 같습니다. 지금, 루트 노드에 removeFailures를 실행하는 것은 전혀 트리를 수정하지 않습니다 (전순 통과하기 전에 일을하고 이후에 같은 결과를 제공합니다).
나는 "root is None"이라고 말할 때 실제로 root를 수정하지 않고, 아마도 temp 변수 이름을 root로 만드는 것일까? 이 경우이 문제를 어떻게 해결할 수 있습니까? 이 추론이 Java에서 작동하지 않습니까?
# Ex.
# 4 4
# / \ / \
# 1 3 1 3
# / \ / \ --> / / \
# 0 0 4 6 0 4 6
# /\ /\ / \
# 3 5 0 0 3 5
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def removeFailures(root):
if root is None:
return True
removeLeft = removeFailures(root.left)
removeRight = removeFailures(root.right)
if root.data == 0 and removeLeft and removeRight:
root = None
return True
return False
def preorder(root):
print root.data
if root.left:
preorder(root.left)
if root.right:
preorder(root.right)
example = TreeNode(4)
example.left = TreeNode(1, TreeNode(0, TreeNode(3), TreeNode(5)), TreeNode(0, TreeNode(0), TreeNode(0)))
example.right = TreeNode(3, TreeNode(4), TreeNode(6))
preorder(example)
print '*************************'
removeFailures(example)
preorder(example) #TODO
- 답변 # 1
- 답변 # 2
재귀 적으로
removeFailures()
에 전화 한 후 자식 노드에서는None
로 설정해야합니다. 그들은 성공적으로 제거 된 경우 :def removeFailures(root): if root is None: return True removeLeft = removeFailures(root.left) removeRight = removeFailures(root.right) # Check if successfully removed children if removeLeft: root.left = None if removeRight: root.right = None if root.data == 0 and removeLeft and removeRight: root = None return True return False
출력 :
4 1 0 3 5 0 0 0 3 4 6 ************************* 4 1 0 3 5 3 4 6
노드 자체를
None
로 설정 부모 노드에 여전히 참조가 있기 때문에 충분하지 않습니다. 따라서 해당 노드에 대한 모든 참조를None
로 설정해야합니다. 제대로 그것을 제거 할 수 있습니다.
트렌드
- OpenCv의 폴더에서 여러 이미지 읽기 (python)
- 파이썬 셀레늄 모든 "href"속성 가져 오기
- html - 자바 스크립트 - 클릭 후 변경 버튼 텍스트 변경
- javascript - 현재 URL에서 특정 div 만 새로 고침/새로 고침
- JSP에 대한 클래스를 컴파일 할 수 없습니다
- git commit - 자식 - 로컬 커밋 된 파일에 대한 변경을 취소하는 방법
- jquery - JavaScript로 현재 세션 값을 얻으시겠습니까?
- JavaScript 변수를 HTML div에 '출력'하는 방법
- javascript - swiperjs에서 정지, 재생 버튼 추가
- python - 문자열에서 특정 문자 제거
트리의 모든 노드에 0이 포함되어 있는지 확인하려면 각 노드를 반복해야합니다. 가능성은
__iter__
를 만드는 것입니다 트리의 모든 노드를 찾은 다음any
를 찾는 방법 내장 함수를 적용하여 모두 0인지 확인합니다. 마지막으로 간단한 재귀 방법으로 왼쪽 및 오른쪽 자식을 확인하고 필요한 경우 제거 할 수 있습니다.트리를 간단하게 만들려면
<시간>kwargs
회전 메소드 또는 긴 일련의 할당 문을 구현하지 않고 내부 구조를 빌드하는 데 사용됩니다.출력 :
전체 트리가 0의 노드를 포함하는 경우를 처리하기 위해
staticmethod
추가 점검을 제공합니다.