检查是否是BST 牛客网 程序员面试金典C++ java Python

检查是否是BST 牛客网 程序员面试金典  C++ java Python

题目描述请实现一个函数，检查一棵二叉树是否为二叉查找树。给定树的根结点指针TreeNode* root，请返回一个bool，代表该树是否为二叉查找树。

C++

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Checker { public: //run:4ms memory:472k bool checkBST(TreeNode* root) { if (NULL == root) return true; if (NULL != root->left){ if (root->left->val > root->val) return false; if (root->left->right && (root->left->right->val > root->val)) return false; } if (NULL != root->right){ if (root->right->val < root->val) return false; if (root->right->left && (root->right->left->val < root->val)) return false; } return checkBST(root->left) && checkBST(root->right); } };

java

import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }*/ public class Checker { // run: 42ms memory:10128k public boolean checkBST(TreeNode root){ if (null == root) return true; if (root.left != null){ if (root.left.val > root.val) return false; if (root.left.right !=null && root.left.right.val > root.val) return false; } if (root.right != null){ if(root.right.val < root.val) return false; if(root.right.left != null && root.right.left.val < root.val) return false; } return checkBST(root.left) && checkBST(root.right); } }

Python

# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Checker: #run:48ms memory:5852k def checkBST(self, root): if None == root: return True if None != root.left: if root.left.val > root.val: return False if None != root.left.right and root.left.right.val > root.val: return False if None != root.right: if root.right.val <root.val: return False if None != root.right.left and root.right.left.val < root.val: return False return self.checkBST(root.left) and self.checkBST(root.right)

 

转载于:https://www.cnblogs.com/vercont/p/10210314.html

相关资源：JAVA上百实例源码以及开源项目