题解 | #判断是不是二叉搜索树#

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
function isValidBST( $root )
{
    $prev = null;
    return inOrder($root, $prev);
}

function inOrder($root, &$prev){
    if($root == null){
        return true;
    }
    $left = inOrder($root->left, $prev);
    if($prev != null && $prev->val > $root->val){
        return false;
    }
    $prev = $root;
    $right = inOrder($root->right, $prev);
    return $left && $right;
}

中序遍历法：如果是二叉搜索树，中序遍历一定是递增的

记住中序遍历获得前一个节点的方法：inOrder($root, &$prev), 注意这个$prev一定传实参