0098. 驗證二叉搜索樹 · ttttt

# 0098. 驗證二叉搜索樹 ## 題目地址(98. 驗證二叉搜索樹) <https://leetcode-cn.com/problems/validate-binary-search-tree/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征：節點的左子樹只包含小于當前節點的數。節點的右子樹只包含大于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。示例 1: 輸入: 2 / \ 1 3 輸出: true 示例 2: 輸入: 5 / \ 1 4 / \ 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]。根節點的值為 5 ，但是其右子節點值為 4 。 ``` ``` ## 前置知識 - 中序遍歷 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 ### 中序遍歷這道題是讓你驗證一棵樹是否為二叉查找樹（BST）。由于中序遍歷的性質`如果一個樹遍歷的結果是有序數組，那么他也是一個二叉查找樹(BST)`, 我們只需要中序遍歷，然后兩兩判斷是否有逆序的元素對即可，如果有，則不是 BST，否則即為一個 BST。 ### 定義法根據定義，一個結點若是在根的左子樹上，那它應該小于根結點的值而大于左子樹最小值；若是在根的右子樹上，那它應該大于根結點的值而小于右子樹最大值。也就是說，每一個結點必須落在某個取值范圍： 1. 根結點的取值范圍為（考慮某個結點為最大或最小整數的情況）：(long\_min, long\_max) 2. 左子樹的取值范圍為：(current\_min, root.value) 3. 右子樹的取值范圍為：(root.value, current\_max) ## 關鍵點解析 - 二叉樹的基本操作（遍歷） - 中序遍歷一個二叉查找樹（BST）的結果是一個有序數組 - 如果一個樹遍歷的結果是有序數組，那么他也是一個二叉查找樹(BST) ## 代碼 ### 中序遍歷 - 語言支持：JS，C++, Java JavaScript Code： ``` <pre class="calibre18">``` /* * @lc app=leetcode id=98 lang=javascript * * [98] Validate Binary Search Tree */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function (root) { if (root === null) return true; if (root.left === null && root.right === null) return true; const stack = [root]; let cur = root; let pre = null; function insertAllLefts(cur) { while (cur && cur.left) { const l = cur.left; stack.push(l); cur = l; } } insertAllLefts(cur); while ((cur = stack.pop())) { if (pre && cur.val <= pre.val) return false; const r = cur.right; if (r) { stack.push(r); insertAllLefts(r); } pre = cur; } return true; }; ``` ``` C++ Code： ``` <pre class="calibre18">``` // 遞歸 class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev = nullptr; return validateBstInorder(root, prev); } private: bool validateBstInorder(TreeNode* root, TreeNode*& prev) { if (root == nullptr) return true; if (!validateBstInorder(root->left, prev)) return false; if (prev != nullptr && prev->val >= root->val) return false; prev = root; return validateBstInorder(root->right, prev); } }; // 迭代 class Solution { public: bool isValidBST(TreeNode* root) { auto s = vector<TreeNode*>(); TreeNode* prev = nullptr; while (root != nullptr || !s.empty()) { while (root != nullptr) { s.push_back(root); root = root->left; } root = s.back(); s.pop_back(); if (prev != nullptr && prev->val >= root->val) return false; prev = root; root = root->right; } return true; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { Stack<Integer> stack = new Stack<> (); TreeNode previous = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (previous != null && root.val <= previous.val ) return false; previous = root; root = root.right; } return true; } } ``` ``` ### 定義法 - 語言支持：C++，Python3, Java, JS C++ Code： ``` <pre class="calibre18">``` /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // 遞歸 class Solution { public: bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } private: bool helper(const TreeNode* root, long min, long max) { if (root == nullptr) return true; if (root->val >= max || root->val <= min) return false; return helper(root->left, min, root->val) && helper(root->right, root->val, max); } }; // 循環 class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr) return true; auto ranges = queue<pair<long, long>>(); ranges.push(make_pair(LONG_MIN, LONG_MAX)); auto nodes = queue<const TreeNode*>(); nodes.push(root); while (!nodes.empty()) { auto sz = nodes.size(); for (auto i = 0; i < sz; ++i) { auto range = ranges.front(); ranges.pop(); auto n = nodes.front(); nodes.pop(); if (n->val >= range.second || n->val <= range.first) { return false; } if (n->left != nullptr) { ranges.push(make_pair(range.first, n->val)); nodes.push(n->left); } if (n->right != nullptr) { ranges.push(make_pair(n->val, range.second)); nodes.push(n->right); } } } return true; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) -> bool: """思路如上面的分析，用Python表達會非常直白 :param root TreeNode 節點 :param area tuple 取值區間 """ if root is None: return True is_valid_left = root.left is None or\ (root.left.val < root.val and area[0] < root.left.val < area[1]) is_valid_right = root.right is None or\ (root.right.val > root.val and area[0] < root.right.val < area[1]) # 左右節點都符合，說明本節點符合要求 is_valid = is_valid_left and is_valid_right # 遞歸下去 return is_valid\ and self.isValidBST(root.left, (area[0], root.val))\ and self.isValidBST(root.right, (root.val, area[1])) ``` ``` Java Code: ``` <pre class="calibre18">``` /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { return helper(root, null, null); } private boolean helper(TreeNode root, Integer lower, Integer higher) { if (root == null) return true; if (lower != null && root.val <= lower) return false; if (higher != null && root.val >= higher) return false; if (!helper(root.left, lower, root.val)) return false; if (!helper(root.right, root.val, higher)) return false; return true; } } ``` ``` JavaScript Code: ``` <pre class="calibre18">``` /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function (root) { if (!root) return true; return valid(root); }; function valid(root, min = -Infinity, max = Infinity) { if (!root) return true; const val = root.val; if (val <= min) return false; if (val >= max) return false; return valid(root.left, min, val) && valid(root.right, val, max); } ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 相關題目 [230.kth-smallest-element-in-a-bst](230.kth-smallest-element-in-a-bst.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)