Tree - 173. Binary Search Tree Iterator

Published on with 0 views and 0 comments

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

 

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

思路:

题目要求写一个bst的迭代器,实现两个接口,输出树中目前最小的值,和树中目前有没有下一个节点。仔细分析会发现,由于bst的根节点比左边的大比右边的小,要从小到达输出,明显就是中序遍历来做这道题,这里采用容器list来当stack,当然也可以自己使用切片和一个栈顶指针来实现一个栈。

代码:

go:

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type BSTIterator struct {
    Stack *list.List
}


func Constructor(root *TreeNode) BSTIterator {
    bsti := BSTIterator{Stack:list.New()}
    bsti.push(root)
    return bsti
}


/** @return the next smallest number */
func (this *BSTIterator) Next() int {
    e := this.Stack.Back()
    cur := e.Value.(*TreeNode)
    this.Stack.Remove(e)

    this.push(cur.Right)
    return cur.Val
}


/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
    return this.Stack.Len() != 0    
}

func (this *BSTIterator) push(node *TreeNode) {
    for node != nil {
        this.Stack.PushBack(node)
        node = node.Left
    }
}


/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

标题:Tree - 173. Binary Search Tree Iterator
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/08/28/1567007098288.html