>

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

    트리의 모든 노드에 0이 포함되어 있는지 확인하려면 각 노드를 반복해야합니다. 가능성은 __iter__ 를 만드는 것입니다  트리의 모든 노드를 찾은 다음 any 를 찾는 방법  내장 함수를 적용하여 모두 0인지 확인합니다. 마지막으로 간단한 재귀 방법으로 왼쪽 및 오른쪽 자식을 확인하고 필요한 경우 제거 할 수 있습니다.

    트리를 간단하게 만들려면 kwargs  회전 메소드 또는 긴 일련의 할당 문을 구현하지 않고 내부 구조를 빌드하는 데 사용됩니다.

    class Tree:
      def __init__(self, **kwargs):
        self.__dict__ = {i:kwargs.get(i) for i in ['left', 'right', 'val']}
      def __iter__(self):
        yield self.val
        yield from ([] if self.left is None else self.left)
        yield from ([] if self.right is None else self.right)
      @staticmethod
      def remove_empty_trees(_t):
        if not any(_t):
           return None
        _t.remove_trees()
        return _t
      def remove_trees(self):
        if not any([] if self.left is None else self.left):
           self.left = None
        else:
           self.left.remove_trees()
        if not any([] if self.right is None else self.right):
           self.right = None
        else:
           self.right.remove_trees()
    
    
    <시간>
    #           4         
    #        /     \    
    #       1       3 
    #       / \    / \  
    #      0   0  4  6
    #     /\  /\            
    #    3 5 0  0
    t = Tree(val=4, left=Tree(val=1, left=Tree(val=0, left=Tree(val=3), right=Tree(val=5)), right=Tree(val=0, left=Tree(val=0), right=Tree(val=0))), right=Tree(val=3, left=Tree(val=4), right=Tree(val=6)))
    new_tree = Tree.remove_empty_trees(t)
    print(print(new_tree.left.right))
    
    

    출력 :

    None
    
    

    전체 트리가 0의 노드를 포함하는 경우를 처리하기 위해 staticmethod  추가 점검을 제공합니다.

  • 답변 # 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 로 설정해야합니다.  제대로 그것을 제거 할 수 있습니다.

  • 이전 파이썬 팬더와 BeautifulSoup을 사용하여 2018 년 위키 백과 테이블을 읽는 방법
  • 다음 Google은 v3 표준 아이콘/그림자 이름을 매핑합니다 (v2의 G_DEFAULT_ICON과 동일)