問題鏈接

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/625/

解題思路

• 二叉樹中序遍歷
• 注意點：初始變量不能寫在遞歸函數(shù)內(nèi)，不然每次都會被初始化為None

錯誤答案

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        preNode = None
        if root:

            if not self.isValidBST(root.left):
                return False

            if preNode and preNode.val >= root.val:
                return False

            preNode = root

            if not self.isValidBST(root.right):
                return False

        return True

正確答案

class Solution(object):
    preNode = None
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if root:

            if not self.isValidBST(root.left):
                return False

            if self.preNode and self.preNode.val >= root.val:
                return False

            self.preNode = root

            if not self.isValidBST(root.right):
                return False

        return True