leetCode ✏Leetcode之PHP版题目解析（173. Binary Search Tree Iterator)
✏描述
给定一棵搜索二叉树，在搜索二叉树上实现迭代搜索，next返回下一个最小节点
✏题目实例
✏题目分析
说白了其实就是对查找二叉树中序遍历的操作。用一个栈来存储即可。
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class BSTIterator {
public $stock=[];
/**
* @param TreeNode $root
*/
function __construct($root) {
while($root){
array_unshift($this->stock,$root);
$root=$root->left;
}
}
/**
* @return the next smallest number
* @return Integer
*/
function next() {
$node=array_shift($this->stock);
$res=$node->val;
if($node->right){
$node=$node->right;
while($node){
array_unshift($this->stock,$node);
$node=$node->left;
}
}
return $res;
}
/**
* @return whether we have a next smallest number
* @return Boolean
*/
function hasNext() {
return !empty($this->stock);
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* $obj = BSTIterator($root);
* $ret_1 = $obj->next();
* $ret_2 = $obj->hasNext();
*/
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)