2022 算法题：设计一个算法判断二叉树是否为二叉排序树
考试时用的 ：区间放缩
利用二叉树的性质，根节点值大于左子树，根节点值小于右子树值
初始区间为无穷，每过1个结点更新子树区间范围
考研时用的数组存放，这里用2叉链表存放，算法思想一样的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    int INF=0x3f3f3f3f;
    //left ，right表示当前节点的范围
    bool dfs(TreeNode *root,int left,int right)
    {
       if(!root)return true;
       if(root->val<=right&&root->val>=left)
       {
           return (dfs(root->left,left,root->val)&&dfs(root->right,root->val,right));
       }else return false;
    }
        //判断是否为二叉排序树

    int pathSum(TreeNode* root) {
        if( dfs(root, -INF,INF))
        cout<<"是二叉排序树"<<endl;
        else 
        cout<<"不是二叉排序树"<<endl;
    }
};

可以在acwing3766下测试

二叉树的带权路径长度

测试数据：

[10, 5, 12, null, null, 11, 13, null, null, null, null]