1.题目：
?2.解答
1）递归算法：
--思路： 比较左子树中的值比根节点的值不小，或 右子树中的值比根节点中的值不大，则返回 false
--代码实现
$this->doCheck($root, PHP_INT_MIN, PHP_INT_MAX);
?/**
? ? * 递归(recursion)的解决方案
? ? * php中最小数值和最大数值怎么表示？PHP_INT_MAXPHP_INT_MIN
? ? ?*/
? ? function doCheck($root, $lowVal, $highVal) {
? ? ? ? if($root === null){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? // 适当的调试，帮助理解和编码
? ? ? ? //var_dump("01", $root->val, $lowVal, $highVal, "\n\n");
? ? ? ? // 一定注意判断下 $lowVal 和 $highVal 为 null的情况
? ? ? ? if(($root->val <= $lowVal)
? ? ? ? || ($root->val >= $highVal)){
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? // 注意是取 逻辑的与
? ? ? ? return $this->doCheck($root->left, $lowVal, $root->val)
? ? ? ? ?&& $this->doCheck($root->right, $root->val, $highVal);
? ? }
-- 注意点：
① php的最小值，最大值分别为 PHP_INT_MIN 和 PHP_INT_MAX
② php是弱语言，里边的 null == 0 会返回 true
③ 最后的 返回表达式里，上下边界的取值
return this->doCheck(this?>doCheck(root->left, $lowVal, $root->val)
&& this->doCheck(this?>doCheck(root->right, $root->val, $highVal);
2）迭代算法
--思路： 使用二叉树的中序遍历，因为是 二叉搜索树，中序遍历的结果应该是一个 升序序列。
-- 代码实现：
/**
? ? * 迭代(iteration)的解决方案: 中序遍历
? ? */
? ? function dieDaiCheck($root){
? ? ? ? if($root === null){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? // 栈数组
? ? ? ? $stack = array();
? ? ? ? $inOrder = null;
? ? ? ? // test?
? ? ? ? $loop = 0;
? ? ? ? while(!empty($stack) || $root != null){
? ? ? ? ? ? // test?
? ? ? ? ? ? $loop ++;
? ? ? ? ? ? while($root !== null){
? ? ? ? ? ? ? ? // 这里放置的是一个对象
? ? ? ? ? ? ? ? $stack[] = $root;
? ? ? ? ? ? ? ? $root = $root->left;
? ? ? ? ? ? }
? ? ? ? ? ? // 出栈
? ? ? ? ? ? $root = array_pop($stack);
? ? ? ? ? ? // 注意php是弱语言， 0 == null 会返回真
? ? ? ? ? ? if($inOrder !== null && $root->val <= $inOrder){
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? ? ? $inOrder = $root->val;
? ? ? ? ? ? $root = $root->right;
? ? ? ? }
? ? ? ? return true;
? ? }
-- 注意点：
① 中序遍历的迭代算法中，使用数据结构 stack来实现，java中建议是 DeQueue,不建议已经过时的 Stack, php中数组表达一切，只是注意 array_pop代表弹栈操作
②php弱语言的性质还要注意
③ 二叉树中序遍历的模板注意背诵，左 * 右