mardi 11 octobre 2016

Recover Binary Tree

For this question on leet code, this code is passing all the test cases.

class Solution(object):
def recoverTree(self, root):
    self.first = None
    self.second = None
    self.prev = TreeNode(float('-inf'))

    self.traverse(root)

    temp = self.first.val
    self.first.val = self.second.val
    self.second.val = temp

def traverse(self, root):
    if not root:
        return
    self.traverse(root.left)
    if not self.first and self.prev.val >= root.val:
        self.first = self.prev
    if self.first and self.prev.val >= root.val:
        self.second = root
    self.prev = root
    self.traverse(root.right)

I have a question about one part of this code.

if not self.first and self.prev.val >= root.val:
    self.first = self.prev
if self.first and self.prev.val >= root.val:
    self.second = root

In this snippet, wont the second condition always be true after the first one has been set. So, you coud write it as:

def not self.first and self.prev.val >= root.val:
    self.first = self.prev
    self.second = root

But if I try this, I will not pass the test cases. Why is it the case? It seem like if we accept the condition for first if statement, and assign self.first, condition for second if statement will always be true. But in reality this seems not to be the case. Can someone please explain whats happening here?

Aucun commentaire:

Enregistrer un commentaire