Блог

Я пытался решить проблему Проверки дерева двоичного поиска в коде Leet.

Мой подход состоял в том , чтобы выполнить обход по порядку и добавить данные в список. Теперь я попытаюсь отсортировать список и сравнить его с исходным списком, чтобы проверить, является ли BST действительным или нет.

Однако при выполнении кода в коде leet, хотя моя логика верна и правильно работает в записной книжке Jupiter, та же логика, похоже, не работает в коде Leet.

Мой код :

 # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root:
            stk = self.inOrder(root,[])
            old_stk = stk
            print(old_stk)
            stk.sort()
            print(stk)
            for i,j in zip(old_stk,stk):
                if i!= j:
                    print('{} :: {}'.format(i,j))
                    return False
                else:
                     print('{} :: {}'.format(i,j))
        return True
            
            
    def inOrder(self,root,trav):
        
        if root:
            trav = self.inOrder(root.left,trav)
            trav.append(root.val)
            trav = self.inOrder(root.right,trav)
        return trav
 

Операция STD для old_stk и stk:

 [1, 5, 3, 4, 6]
[1, 3, 4, 5, 6]
1 :: 1
3 :: 3
4 :: 4
5 :: 5
6 :: 6
 

Понятно, что и список, и нет, я пытался использовать return stk == old_stk, а также повторять элемент за элементом, но я получаю неверный вывод.

Верна ли моя логика , или кто-нибудь может указать, где я ошибся ?

Спасибо!