87. Remove Node in Binary Search Tree

1482 단어

제목.


https://www.lintcode.com/problem/remove-node-in-binary-search-tree/description?_from=ladder&&fromId=2

이루어지다

  • 먼저 트리를 중순으로 한 번 훑어보고 삭제할 노드를 필터
  • 중순으로 훑어본 결과 새 나무를 재구성하여 새 나무 루트
  • 로 되돌아오기

    코드

    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    
    
    class Solution:
        """
        @param: root: The root of the binary search tree.
        @param: value: Remove the node with given value.
        @return: The root of the binary search tree after removal.
        """
        inorder_results = []
    
        def removeNode(self, root, value):
            #         
            self.inorder(root, value)
            #             
            new_root = self.build_tree(0, len(self.inorder_results) - 1)
    
            return new_root
    
        def inorder(self, root, value):
            if root is None:
                return
    
            self.inorder(root.left, value)
            if root.val != value:
                self.inorder_results.append(root.val)
            self.inorder(root.right, value)
    
        def build_tree(self, left, right):
            if left == right:
                return TreeNode(self.inorder_results[left])
    
            if left > right:
                return None
    
            mid = (left + right) // 2
            node = TreeNode(self.inorder_results[mid])
            node.left = self.build_tree(left, mid - 1)
            node.right = self.build_tree(mid + 1, right)
    
            return node
    

    좋은 웹페이지 즐겨찾기