leetcode 98 驗證二叉搜尋樹

驗證二叉搜尋樹

二叉樹的題目好難啊，思路不是很清晰。

首先分析這個題目，BFS樹要求右子樹的所有節點都大于目前節點值，左子樹的所有節點都小于目前節點。

想一下，右子樹的最小值，應該是右子樹的最最最左側的一個葉節點，左子樹的最大值應該是最最最右側的葉節點。從下往上似乎不好比較。

如果我們隻是考慮每一個小的二叉樹。也就是隻有三個節點的。什麼情況下才是bfs呢？

1. 右子樹是bfs
2. 左子樹是bfs
3. 目前節點值（大于或小于）對應的值。也就是說，是把目前節點值于上一個節點值做比較。

需要注意的是：

• 初始值的設計，也就是根節點。根節點一定是滿足的，隻需要

  root.val>float('-inf') and root.val<float('inf')

• 每一次對應的傳遞值也要注意，
• 對于右節點，需要更改最小值等于父節點的val。保證右節點值大于父節點。
• 對于左節點，需要更改最大值等于父節點的val，保證左節點值小于父節點。

# 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
        """
        # 判斷到目前是不是bfs，是就true 不是false
        def dfs(root,maxval, minval):  
            if not root:
                return True
            val = root.val
            if val <= minval or val >= maxval:
                return False
            return dfs(root.left, val, minval) and dfs(root.right, maxval, val)

        return dfs(root,float('inf'),float('-inf'))
           

遞歸子函數的設計問題，每一次一定要想清楚，函數的設計目的是什麼，輸入是什麼，傳回值是什麼。