<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 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">``` <span class="hljs-title">/* * @lc app=leetcode id=98 lang=javascript * * [98] Validate Binary Search Tree */</span> <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @return {boolean} */</span> <span class="hljs-keyword">var</span> isValidBST = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (root.left === <span class="hljs-params">null</span> && root.right === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">const</span> stack = [root]; <span class="hljs-keyword">let</span> cur = root; <span class="hljs-keyword">let</span> pre = <span class="hljs-params">null</span>; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">insertAllLefts</span>(<span class="hljs-params">cur</span>) </span>{ <span class="hljs-keyword">while</span> (cur && cur.left) { <span class="hljs-keyword">const</span> l = cur.left; stack.push(l); cur = l; } } insertAllLefts(cur); <span class="hljs-keyword">while</span> ((cur = stack.pop())) { <span class="hljs-keyword">if</span> (pre && cur.val <= pre.val) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">const</span> r = cur.right; <span class="hljs-keyword">if</span> (r) { stack.push(r); insertAllLefts(r); } pre = cur; } <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">// 遞歸</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode* root)</span> </span>{ TreeNode* prev = <span class="hljs-params">nullptr</span>; <span class="hljs-keyword">return</span> validateBstInorder(root, prev); } <span class="hljs-keyword">private</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">validateBstInorder</span><span class="hljs-params">(TreeNode* root, TreeNode*& prev)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (!validateBstInorder(root->left, prev)) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (prev != <span class="hljs-params">nullptr</span> && prev->val >= root->val) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; prev = root; <span class="hljs-keyword">return</span> validateBstInorder(root->right, prev); } }; <span class="hljs-title">// 迭代</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">auto</span> s = <span class="hljs-params">vector</span><TreeNode*>(); TreeNode* prev = <span class="hljs-params">nullptr</span>; <span class="hljs-keyword">while</span> (root != <span class="hljs-params">nullptr</span> || !s.empty()) { <span class="hljs-keyword">while</span> (root != <span class="hljs-params">nullptr</span>) { s.push_back(root); root = root->left; } root = s.back(); s.pop_back(); <span class="hljs-keyword">if</span> (prev != <span class="hljs-params">nullptr</span> && prev->val >= root->val) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; prev = root; root = root->right; } <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode root)</span> </span>{ Stack<Integer> stack = <span class="hljs-keyword">new</span> Stack<> (); TreeNode previous = <span class="hljs-keyword">null</span>; <span class="hljs-keyword">while</span> (root != <span class="hljs-keyword">null</span> || !stack.isEmpty()) { <span class="hljs-keyword">while</span> (root != <span class="hljs-keyword">null</span>) { stack.push(root); root = root.left; } root = stack.pop(); <span class="hljs-keyword">if</span> (previous != <span class="hljs-keyword">null</span> && root.val <= previous.val ) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; previous = root; root = root.right; } <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; } } ``` ``` ### 定義法 - 語言支持:C++,Python3, Java, JS C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-title">// 遞歸</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">return</span> helper(root, LONG_MIN, LONG_MAX); } <span class="hljs-keyword">private</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">helper</span><span class="hljs-params">(<span class="hljs-keyword">const</span> TreeNode* root, <span class="hljs-keyword">long</span> min, <span class="hljs-keyword">long</span> max)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (root->val >= max || root->val <= min) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">return</span> helper(root->left, min, root->val) && helper(root->right, root->val, max); } }; <span class="hljs-title">// 循環</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">auto</span> ranges = <span class="hljs-params">queue</span><pair<<span class="hljs-keyword">long</span>, <span class="hljs-keyword">long</span>>>(); ranges.push(make_pair(LONG_MIN, LONG_MAX)); <span class="hljs-keyword">auto</span> nodes = <span class="hljs-params">queue</span><<span class="hljs-keyword">const</span> TreeNode*>(); nodes.push(root); <span class="hljs-keyword">while</span> (!nodes.empty()) { <span class="hljs-keyword">auto</span> sz = nodes.size(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">0</span>; i < sz; ++i) { <span class="hljs-keyword">auto</span> range = ranges.front(); ranges.pop(); <span class="hljs-keyword">auto</span> n = nodes.front(); nodes.pop(); <span class="hljs-keyword">if</span> (n->val >= range.second || n->val <= range.first) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } <span class="hljs-keyword">if</span> (n->left != <span class="hljs-params">nullptr</span>) { ranges.push(make_pair(range.first, n->val)); nodes.push(n->left); } <span class="hljs-keyword">if</span> (n->right != <span class="hljs-params">nullptr</span>) { ranges.push(make_pair(n->val, range.second)); nodes.push(n->right); } } } <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for a binary tree node.</span> <span class="hljs-title"># class TreeNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.left = None</span> <span class="hljs-title"># self.right = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(self, root: TreeNode, area: tuple=<span class="hljs-params">(-float<span class="hljs-params">(<span class="hljs-string">'inf'</span>)</span>, float<span class="hljs-params">(<span class="hljs-string">'inf'</span>)</span>)</span>)</span> -> bool:</span> <span class="hljs-string">"""思路如上面的分析,用Python表達會非常直白 :param root TreeNode 節點 :param area tuple 取值區間 """</span> <span class="hljs-keyword">if</span> root <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> is_valid_left = root.left <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span>\ (root.left.val < root.val <span class="hljs-keyword">and</span> area[<span class="hljs-params">0</span>] < root.left.val < area[<span class="hljs-params">1</span>]) is_valid_right = root.right <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span>\ (root.right.val > root.val <span class="hljs-keyword">and</span> area[<span class="hljs-params">0</span>] < root.right.val < area[<span class="hljs-params">1</span>]) <span class="hljs-title"># 左右節點都符合,說明本節點符合要求</span> is_valid = is_valid_left <span class="hljs-keyword">and</span> is_valid_right <span class="hljs-title"># 遞歸下去</span> <span class="hljs-keyword">return</span> is_valid\ <span class="hljs-keyword">and</span> self.isValidBST(root.left, (area[<span class="hljs-params">0</span>], root.val))\ <span class="hljs-keyword">and</span> self.isValidBST(root.right, (root.val, area[<span class="hljs-params">1</span>])) ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isValidBST</span><span class="hljs-params">(TreeNode root)</span> </span>{ <span class="hljs-keyword">return</span> helper(root, <span class="hljs-keyword">null</span>, <span class="hljs-keyword">null</span>); } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">helper</span><span class="hljs-params">(TreeNode root, Integer lower, Integer higher)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; <span class="hljs-keyword">if</span> (lower != <span class="hljs-keyword">null</span> && root.val <= lower) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">if</span> (higher != <span class="hljs-keyword">null</span> && root.val >= higher) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">if</span> (!helper(root.left, lower, root.val)) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">if</span> (!helper(root.right, root.val, higher)) <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>; <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>; } } ``` ``` JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @return {boolean} */</span> <span class="hljs-keyword">var</span> isValidBST = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">return</span> valid(root); }; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">valid</span>(<span class="hljs-params">root, min = -Infinity, max = Infinity</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">const</span> val = root.val; <span class="hljs-keyword">if</span> (val <= min) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> (val >= max) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看