LeetCode Validate Binary Search Tree

LeetCode解題之Validate Binary Search Tree

原題

判斷一棵二叉搜索樹是否有效。有效是指每個節點的值大於左節點，小於右節點（如果有對應節點的話），且它的左節點和右節點也滿足這種條件。

注意點：

例子：

輸入:

  2
 / \
1   3

輸出: True

解題思路

在 Binary Tree Inorder Traversal 的基礎上進行了修改。在樹的中序遍歷中，節點的順序是左節點、根節點、右節點。這就說明一棵二叉搜索樹要符合要求時，它的中序遍歷序列一定是遞增的。如果在中序遍歷中出現前面的節點大於後面的節點，則說明不符合要求。

AC源碼

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack = []
        curr = root
        prev = None
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left

            if stack:
                curr = stack.pop()
                if prev and curr.val <= prev.val:
                    return False
                prev = curr
                curr = curr.right
        return True


if __name__ == "__main__":
    None