欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)LeetCode(98.驗(yàn)證二叉搜索樹)

 更新時(shí)間:2021年07月19日 15:47:01   作者:Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(98.驗(yàn)證二叉搜索樹),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 98. Validate Binary Search Tree 驗(yàn)證二叉搜索樹

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
2
/ \
1   3
Output: true

Example 2:

    5
/ \
1   4
/ \
3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.

這道驗(yàn)證二叉搜索樹有很多種解法,可以利用它本身的性質(zhì)來做,即左<根<右,也可以通過利用中序遍歷結(jié)果為有序數(shù)列來做,下面我們先來看最簡單的一種,就是利用其本身性質(zhì)來做,初始化時(shí)帶入系統(tǒng)最大值和最小值,在遞歸過程中換成它們自己的節(jié)點(diǎn)值,用long代替int就是為了包括int的邊界條件,代碼如下:

C++ 解法一:

// Recursion without inorder traversal
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    bool isValidBST(TreeNode* root, long mn, long mx) {
        if (!root) return true;
        if (root->val <= mn || root->val >= mx) return false;
        return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
    }
};

Java 解法一:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean valid(TreeNode root, long low, long high) {
        if (root == null) return true;
        if (root.val <= low || root.val >= high) return false;
        return valid(root.left, low, root.val) && valid(root.right, root.val, high);
    }
}

這題實(shí)際上簡化了難度,因?yàn)橛械臅r(shí)候題目中的二叉搜索樹會(huì)定義為左<=根<右,而這道題設(shè)定為一般情況左<根<右,那么就可以用中序遍歷來做。因?yàn)槿绻蝗サ糇?根這個(gè)條件的話,那么下邊兩個(gè)數(shù)用中序遍歷無法區(qū)分:

   20       20
/           \
20           20

它們的中序遍歷結(jié)果都一樣,但是左邊的是 BST,右邊的不是 BST。去掉等號(hào)的條件則相當(dāng)于去掉了這種限制條件。下面來看使用中序遍歷來做,這種方法思路很直接,通過中序遍歷將所有的節(jié)點(diǎn)值存到一個(gè)數(shù)組里,然后再來判斷這個(gè)數(shù)組是不是有序的,代碼如下:

C++ 解法二:

// Recursion
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        vector<int> vals;
        inorder(root, vals);
        for (int i = 0; i < vals.size() - 1; ++i) {
            if (vals[i] >= vals[i + 1]) return false;
        }
        return true;
    }
    void inorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
};

Java 解法二:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) >= list.get(i + 1)) return false;
        }
        return true;
    }
    public void inorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

下面這種解法跟上面那個(gè)很類似,都是用遞歸的中序遍歷,但不同之處是不將遍歷結(jié)果存入一個(gè)數(shù)組遍歷完成再比較,而是每當(dāng)遍歷到一個(gè)新節(jié)點(diǎn)時(shí)和其上一個(gè)節(jié)點(diǎn)比較,如果不大于上一個(gè)節(jié)點(diǎn)那么則返回 false,全部遍歷完成后返回 true。代碼如下:

C++ 解法三:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = NULL;
        return inorder(root, pre);
    }
    bool inorder(TreeNode* node, TreeNode*& pre) {
        if (!node) return true;
        bool res = inorder(node->left, pre);
        if (!res) return false;
        if (pre) {
            if (node->val <= pre->val) return false;
        }
        pre = node;
        return inorder(node->right, pre);
    }
};

當(dāng)然這道題也可以用非遞歸來做,需要用到棧,因?yàn)橹行虮闅v可以非遞歸來實(shí)現(xiàn),所以只要在其上面稍加改動(dòng)便可,代碼如下:

C++ 解法四:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode *p = root, *pre = NULL;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (pre && p->val <= pre->val) return false;
            pre = p;
            p = p->right;
        }
        return true;
    }
};

Java 解法四:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode p = root, pre = null;
        while (p != null || !s.empty()) {
            while (p != null) {
                s.push(p);
                p = p.left;
            }
            p = s.pop();
            if (pre != null && p.val <= pre.val) return false;
            pre = p;
            p = p.right;
        }
        return true;
    }
}

最后還有一種方法,由于中序遍歷還有非遞歸且無棧的實(shí)現(xiàn)方法,稱之為 Morris 遍歷,可以參考博主之前的博客 Binary Tree Inorder Traversal,這種實(shí)現(xiàn)方法雖然寫起來比遞歸版本要復(fù)雜的多,但是好處在于是 O(1) 空間復(fù)雜度,參見代碼如下:

C++ 解法五:

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root) return true;
        TreeNode *cur = root, *pre, *parent = NULL;
        bool res = true;
        while (cur) {
            if (!cur->left) {
                if (parent && parent->val >= cur->val) res = false;
                parent = cur;
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    if (parent->val >= cur->val) res = false;
                    parent = cur;
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(98.驗(yàn)證二叉搜索樹)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)驗(yàn)證二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 基于c++的中國象棋游戲設(shè)計(jì)與實(shí)現(xiàn)

    基于c++的中國象棋游戲設(shè)計(jì)與實(shí)現(xiàn)

    這篇文章主要介紹了基于c++的中國象棋游戲設(shè)計(jì)與實(shí)現(xiàn),主要操作是possibleMove(int?x,?int?y),通過整個(gè)棋盤每個(gè)位置上的信息、中國象棋的規(guī)則來獲得位置(x,?y)這個(gè)棋子可以移動(dòng)到的位置,需要的朋友可以參考一下
    2022-02-02
  • C++中HTTP?代理服務(wù)器的設(shè)計(jì)與實(shí)現(xiàn)詳解

    C++中HTTP?代理服務(wù)器的設(shè)計(jì)與實(shí)現(xiàn)詳解

    代理服務(wù)器,即允許一個(gè)網(wǎng)絡(luò)終端(一般為客戶端)通過這個(gè)服務(wù)與另一?個(gè)網(wǎng)絡(luò)終端(一般為服務(wù)器)進(jìn)行非直接的連接,下面我們就來看看如何使用C++設(shè)計(jì)與實(shí)現(xiàn)一個(gè)HTTP?代理服務(wù)器吧
    2024-01-01
  • C++中按引用傳遞參數(shù)的好處有哪些

    C++中按引用傳遞參數(shù)的好處有哪些

    這篇文章主要介紹了C++中按引用傳遞參數(shù)的好處有哪些,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • 在C++中自定義宏的簡單方法

    在C++中自定義宏的簡單方法

    這篇文章主要介紹了在C++中自定義宏的簡單方法,作者建議使用類似定義函數(shù)一樣的方法來定義宏,需要的朋友可以參考下
    2015-07-07
  • C語言實(shí)現(xiàn)井字棋游戲

    C語言實(shí)現(xiàn)井字棋游戲

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)井字棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-04-04
  • Qt數(shù)據(jù)庫應(yīng)用之超級(jí)自定義委托

    Qt數(shù)據(jù)庫應(yīng)用之超級(jí)自定義委托

    Qt中需要用到自定義委托的情形很多,比如提供下拉框選擇,進(jìn)度條展示下載進(jìn)度啥的,默認(rèn)的單元格是沒有這些效果的,需要自己單獨(dú)用委托的形式來展示。本文將為大家介紹Qt中如何進(jìn)行超級(jí)自定義委托,需要的可以參考一下
    2022-03-03
  • 最新評(píng)論