173.md

:pencil2:Leetcode之PHP版题目解析（173. Binary Search Tree Iterator)

2019-09-26 吴亲库里 库里的深夜食堂

---

:pencil2:描述

给定一棵搜索二叉树，在搜索二叉树上实现迭代搜索，next返回下一个最小节点

---

:pencil2:题目实例

​

:pencil2:题目分析

说白了其实就是对查找二叉树中序遍历的操作。用一个栈来存储即可。

/**
 * 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();
 */

---

联系

​