二叉树---检查是否为BST

今天开始为校招做准备。

本文的实现代码可以在我的github中找到。

题目来自牛客网：

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

分析思路：只要节点的值大于左子节点和左子节点的右子节点，小于右子节点和右子节点的左子节点即可。

这样用递归很容易实现。

代码：

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 { public boolean checkBST(TreeNode root) { // write code here if(root==null) 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); } }