程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode_Validate Binary Search Tree

leetcode_Validate Binary Search Tree

編輯:C++入門知識

leetcode_Validate Binary Search Tree


題目描述

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.

解題思路

題目的意思就是判斷一個給定的二叉樹是不是二叉搜索樹,二叉搜索樹要求對每個節點,其左兒子節點數值小於父節點數值,右兒子節點數值大於父節點數值,並且左側子樹上的數值都小於父節點,右側子樹所有數值都大於父節點,也就是按此規則嚴格有序的,實際上我們中序遍歷便可得到從小到大排序的元素序列,這裡我們通過對中序遍歷得到的List進行判斷是否有來決定此二叉樹是否為二叉搜索樹。(這裡涉及二叉搜索樹和線序遍歷有序兩個概念的充分必要性,可以自行證明)

詳細代碼

二叉樹的前中後序遍歷通過遞歸可以很簡單地寫出代碼,leetcode上也有要求迭代實現的,後續也會講解。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
        //Validate Binary Search Tree
    //Given a binary tree, determine if it is a valid binary search tree (BST).
    public boolean isValidBST(TreeNode root) 
    {


        ArrayList resultList = inorderTraversal(root);
        if(resultList.size()>=2)
        {
            for (int i = 0; i < resultList.size()-1; i++)
            {
                if (resultList.get(i)>=resultList.get(i+1))
                {
                    return false;
                }
            }
        }
            return true;

    }

    //recursively do it  middle order
  public ArrayList inorderTraversal(TreeNode root) 
  {
    ArrayList results = new ArrayList();
    if(root == null)
    {
        return results;
    }
    else 
    {   
        results.addAll(inorderTraversal(root.left));//traverse left 
        results.add(root.val);//traverse the parent node
        results.addAll(inorderTraversal(root.right));//traverse right
        return results;
    }
  }
}

總結

這裡需要理解二叉搜索樹的概念,類似地如何建立二叉搜索樹(BST),二叉搜索樹地插入刪除操作也是需要研究的,當然有興趣滴可以去研究下,平衡二叉樹(AVL),紅黑樹(RBT),字典樹(TRIE)等。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved