「プログラマ面接金典」はBSTかどうかを検査します。

【声明：著作権所有、転載は出所を明記してください。商業用途に使用しないでください。 連絡先:[email protected]テーマリンク：http://www.nowcoder.com/practice/536c0199151245f897da2c5390930657?rp=1&ru=/ta/cracking-the-coding-interview&ql=/ta/cracking-the-coding-innterview/questionn-rankingテーマの説明は一つの関数を実現してください。一本の二叉樹が二叉で木を探しているかどうかを確認します。ツリーのルートノードポインタTreeNode*rootが与えられた場合、ツリーが二叉であるかどうかを示すブックに戻ります。考え方は下を検索する時に、この時の左の結点を判断し、右の結点と親のノードが二叉で木を検索する法則を満たしているかどうかを判断すればいいです。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Checker
{
	public:
		bool checkBST(TreeNode *root)
		{
			// write code here
			return isBST(root);
		}
		bool isBST(TreeNode *root)
		{
			if(root==nullptr)
				return true;
			bool left = true,right=true;
			if(root->left && root->left->val>root->val)
				return false;
			if(root->right && root->right->val<root->val)
				return false;
			if(root->left)
				left = isBST(root->left);
			if(root->right)
				right = isBST(root->right);
			return left && right;
		}
};