【Leetcode】98. 驗證二叉搜索樹

nidaye 發布于2019-08-16 15:10 / 2601人閱讀

摘要：題目給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。所有左子樹和右子樹自身必須也是二叉搜索樹。題解這道題目主要是利用二叉搜索樹的一個性質二叉搜索樹的中序遍歷結果是一個升序的序列。

題目

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設一個二叉搜索樹具有如下特征：

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

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

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

示例 1:

輸入:
    2
   / 
  1   3
輸出: true

示例 2:

輸入:
    5
   / 
  1   4
     / 
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
     根節點的值為 5 ，但是其右子節點值為 4 。

題解

這道題目主要是利用二叉搜索樹的一個性質：
二叉搜索樹的中序遍歷結果是一個升序的序列。
那么問題轉變成：中序遍歷 + 驗證是不是升序.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List inPrint(TreeNode root, List res) {
        if (root != null) {
            inPrint(root.left, res);
            res.add(root.val);
            inPrint(root.right, res);
        }
        return res;
    }
    
    public boolean isValidBST(TreeNode root) {
        List res = inPrint(root, new LinkedList<>());
        if (res.size() == 1) {
            return true;
        }
        for (int i = 1; i < res.size(); i++) {
            if (res.get(i) <= res.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

GPU云服務器云服務器二叉樹排序樹規則二叉查找樹二叉排序樹二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73319.html

LeetCode 之 JavaScript 解答第98題 —— 驗證二叉搜索樹

摘要：小鹿題目驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用戶84 2019-08-23 17:12 評論0 收藏0
通過幾道題目學習二叉搜索樹

摘要：根據這個特征，用二分法來將有序數組轉換為一顆二叉搜索樹。邊界條件向下取整得到中間值遞歸二分法接下來我們驗證下一棵樹是否滿足二叉搜索樹。二驗證二叉搜索樹相關題目驗證二叉搜索樹中等思路就是，中序遍歷如果滿足遞增的就行。二叉樹大家都知道，二叉搜索樹滿足以下特征：節點的左子樹只包含小于當前節點的數節點的右子樹只包含大于當前節點的數所有左子樹和右子樹自身必須也是二叉搜索樹二叉搜索樹也叫...

Steven 2019-08-23 13:42 評論0 收藏0
Leetcode打卡——二叉搜索樹（共8題）

摘要：也就是說，有個節點的平衡二叉搜索樹，它的高度是。以搜索操作為例，如果二叉搜索樹的高度為，則時間復雜度為。二叉搜索樹的高度的確很重要。樹集合，中的或者中的，是由高度平衡的二叉搜索樹實現的。 ...

Olivia 2021-11-15 11:38 評論0 收藏0
＜LeetCode天梯＞Day031 驗證二叉搜索樹（遞歸+中序遍歷） | 初級算法 | Pytho

摘要：有效二叉搜索樹定義如下節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值，根節點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 評論0 收藏0
[Leetcode] Validate Binary Search Tree 驗證二叉搜索樹

摘要：注意這里的結構和不同的二叉樹遍歷一樣，如果到空節點就返回，否則遞歸遍歷左節點和右節點。唯一不同是加入了和，所以要在遞歸之前先判斷是否符合和的條件。代碼如果該節點大于上限返回假如果該節點小于下限返回假遞歸判斷左子樹和右子樹 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

fuchenxuan 2019-08-14 12:40 評論0 收藏0