APP手机端电子商务网站建设广告软文外链平台

根据二叉搜索树的特性，我们使用中序遍历，保证节点按从小到大的顺序遍历。既然要验证，就是看在中序遍历的条件下，各个节点的大小关系是否符合二叉搜索树的特性。双指针法和适合解决这个问题，一个指针指向当前节点，另一个指针指向前一个节点(指的是按照中序遍历顺序的前一个节点)，不断后移两个指针，两两进行比较。这只是大致思路，大家可以结合我的代码以及注释加以理解。

代码及注释如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* pre = NULL;//题目属于要验证二叉树的特性，递归函数返回值用布尔类型3比较适合bool isValidBST(TreeNode* root) {if(root == NULL) return true;//递归左子树bool judge1 = isValidBST(root -> left);if(pre == NULL){pre = root;//将pre从空节点移动到叶子结点}else{if(root -> val > pre -> val){pre = root;//后移pre}else{return false;}}//递归右子树bool judge2 = isValidBST(root -> right);return judge1 && judge2;}
};