專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友曬出了華為在上海青浦的工作餐，被網友調侃太貴了，看到第一眼的時候我感到很詫異，倒不是覺得它貴，而是覺得工作餐不應該是免費的嗎？我之前工作有兩家公司也都是提供工作餐，一家是在手機上自己點，午飯的時候會打包好統一送過來，還一種是送過來我們自己去盛的，都是免費的。即便是在十多年前我在寒暑假打工的的時候，工作餐也都是免費的。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第98：驗證二叉搜索樹。

問題描述

來源：LeetCode第98題

難度：中等

給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹。

有效二叉搜索樹定義如下：

1，節點的左子樹只包含小于當前節點的數。

2，節點的右子樹只包含大于當前節點的數。

3，所有左子樹和右子樹自身必須也是二叉搜索樹。

示例1：

輸入：root = [2,1,3] 輸出：true

示例2：

輸入：root = [5,1,4,null,null,3,6] 輸出：false 解釋：根節點的值是 5 ，但是右子節點的值是 4 。

• 樹中節點數目范圍在[1, 10^4] 內

• -2^31 <= Node.val <= 2^31 - 1

問題分析

這題讓驗證二叉搜索樹是否有效，我們知道二叉搜索樹有一個重要的特性就是它的 中序遍歷結果一定是有序的（遞增的） ，我們對二叉樹進行中序遍歷，如果結果是遞增的，那么它就是一顆有效的二叉搜索樹，否則不是二叉搜索樹。

這里我們沒必要遍歷二叉樹的全部節點，按照中序遍歷的方式每次和遍歷的前一個節點比較，如果當前節點的值小于等于前一個節點的值，說明不是遞增的，不是二叉搜索樹，直接返回false即可。

JAVA：

// 前一個結點 TreeNode prev; public boolean isValidBST(TreeNode root) {     if (root == null)         return true;     if (!isValidBST(root.left))// 遞歸左子樹是否是二叉搜索樹         return false;     // 訪問當前節點：如果當前節點小于等于中序遍歷的前一個節點直接返回false。     if (prev != null && prev.val >= root.val)         return false;     prev = root;     // 遞歸右子樹是否是二叉搜索樹     return isValidBST(root.right); }

C++：

public:     // 前一個結點     TreeNode *prev;     bool isValidBST(TreeNode *root) {         if (root == nullptr)             return true;         if (!isValidBST(root->left))// 遞歸左子樹是否是二叉搜索樹             return false;         // 訪問當前節點：如果當前節點小于等于中序遍歷的前一個節點直接返回false。         if (prev && prev->val >= root->val)             return false;         prev = root;         // 遞歸右子樹是否是二叉搜索樹         return isValidBST(root->right);     }

Python：

def isValidBST(self, root: Optional[TreeNode]) -> bool:     prev = None  # 前一個結點     def helper(node):         nonlocal prev         if node is None:             return True         if not helper(node.left):  # 遞歸左子樹是否是二叉搜索樹             return False         # 訪問當前節點：如果當前節點小于等于中序遍歷的前一個節點直接返回false。         if prev is not None and prev.val >= node.val:             return False         prev = node         # 遞歸右子樹是否是二叉搜索樹         return helper(node.right)     return helper(root)

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。