Simple Python Code using iteration in-order Traversal


  • 0
    C

    Here is my solution using iteration In-order Traversal.
    The basic idea is the traversal result should follow increase order, where node first should should always be smaller than node visited later. I used two stacks for recursion and value tracking.

    class Solution:
    # @param root, a tree node
    # @return a boolean
    def isValidBST(self, root):
        if root is None: return True
        
        # two stacks for tracking nodes and values
        stack = [root.right, root.val, root.left]
        vals = []
        
        while stack:
            node = stack.pop()
            if node is None: continue
            elif type(node) is int:
                # previous val should always smaller than current one
                if vals and vals[-1] >= node:
                    return False
                else:
                    vals.append(node)
            else:
                if node.right: stack.append(node.right)
                stack.append(node.val)
                if node.left: stack.append(node.left)
        return True

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.