【408DS算法题】033基础-判断二叉树是否是二叉排序树

题目

给定二叉树的根节点root，判断该二叉树是否是二叉排序树。

---

分析实现

二叉排序树（BST/二叉搜索树）：对于每个节点，其左子树中所有节点的值都小于当前结点的值，其右子树中所有节点的值都大于当前结点的值；左子树和右子树本身也是二叉搜索树。

在二叉排序树的定义中含有着递归的思想 - “左子树和右子树本身也是二叉搜索树”，因此可以使用递归函数来尝试实现。

具体实现如下：

// 判断BST工具函数
bool isBSTUtil(BTNode* cur, int min, int max){if(cur==NULL)return true;if(cur->val<min || cur->val>max) return false;return isBSTUtil(cur->left, min, cur->val) && isBSTUtil(cur->right, cur->val, max);
}// 判断二叉搜索树
bool isBST(BTNode *root){return isBSTUtil(root, INT_MIN, INT_MAX);
}

---

总结

以上就是利用先序遍历判断二叉排序树的实现，同理也可以利用中序遍历实现判断BST的工具函数（欢迎在评论区讨论交流！）。

特别注意的是，本题有一个常见的错误思路，就是依次判断每个结点：

bool isBST(BTNode *root){if(root==nullptr) return true;if(root->left && root->left->val>=root->val)return false;if(root->right && root->right->val<=root->val)return false;return isBST(root->left) && isBST(root->right);
}

此思路对单个结点的判断并没有错误，但BST要求每个顶点的左子树均大于当前结点，这种写法无法达到这一要求。如：

根据上面的写法该二叉树会被判定为BST，但结点10不满足10 < {15, 6, 20}。