173. Binary Search Tree Iterator

leetcode medium

#array#csharp#design#leetcode#medium#recursion#search#sort#tree#two-pointers

Task

Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order:

BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST.

boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false.

int next(): Перемещает указатель вправо, затем возвращает число на указателе.

Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST.

Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число.

Пример:

Input

["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]

[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);

bSTIterator.next(); // return 3

bSTIterator.next(); // return 7

bSTIterator.hasNext(); // return True

bSTIterator.next(); // return 9

bSTIterator.hasNext(); // return True

bSTIterator.next(); // return 15

bSTIterator.hasNext(); // return True

bSTIterator.next(); // return 20

bSTIterator.hasNext(); // return False

C# solution

matched/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; left = null; right = null; }
}
public class BSTIterator {
    private List<int> nodesSorted;
    private int index;
    private void Inorder(TreeNode root) {
        if (root == null) return;
        Inorder(root.left);
        nodesSorted.Add(root.val);
        Inorder(root.right);
    }
    public BSTIterator(TreeNode root) {
        nodesSorted = new List<int>();
        index = -1;
        Inorder(root);
    }
    public int Next() {
        return nodesSorted[++index];
    }
    public bool HasNext() {
        return index + 1 < nodesSorted.Count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; left = null; right = null; }
}
public class BSTIterator {
    private List<int> nodesSorted;
    private int index;
    private void Inorder(TreeNode root) {
        if (root == null) return;
        Inorder(root.left);
        nodesSorted.push_back(root.val);
        Inorder(root.right);
    }
    public BSTIterator(TreeNode root) {
        nodesSorted = new List<int>();
        index = -1;
        Inorder(root);
    }
    public int Next() {
        return nodesSorted[++index];
    }
    public bool HasNext() {
        return index + 1 < nodesSorted.size();
    }
}

Java solution

matched/original

class BSTIterator {
    ArrayList<Integer> nodesSorted;
    int index;

    public BSTIterator(TreeNode root) {
        this.nodesSorted = new ArrayList<Integer>();
        this.index = -1;
        this._inorder(root);
    }

    private void _inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        this._inorder(root.left);
        this.nodesSorted.add(root.val);
        this._inorder(root.right);
    }

    public int next() {
        return this.nodesSorted.get(++this.index);
    }

    public boolean hasNext() {
        return this.index + 1 < this.nodesSorted.size();
    }
}

JavaScript solution

matched/original

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BSTIterator {
    constructor(root) {
        this.nodesSorted = [];
        this.index = -1;
        this._inorder(root);
    }

    _inorder(root) {
        if (root === null) {
            return;
        }

        this._inorder(root.left);
        this.nodesSorted.push(root.val);
        this._inorder(root.right);
    }

    next() {
        return this.nodesSorted[++this.index];
    }

    hasNext() {
        return this.index + 1 < this.nodesSorted.length;
    }
}

Python solution

matched/original

class TreeNode:
    def __init__(self, x: int):
        self.val = x
        self.left = None
        self.right = None

class BSTIterator:
    def __init__(self, root: TreeNode):
        self.nodes_sorted = []
        self.index = -1
        self._inorder(root)

    def _inorder(self, root: TreeNode) -> None:
        if not root:
            return
        self._inorder(root.left)
        self.nodes_sorted.append(root.val)
        self._inorder(root.right)

    def next(self) -> int:
        self.index += 1
        return self.nodes_sorted[self.index]

    def hasNext(self) -> bool:
        return self.index + 1 < len(self.nodes_sorted)

Go solution

matched/original

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type BSTIterator struct {
    nodesSorted []int
    index       int
}

func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{nodesSorted: []int{}, index: -1}
    iterator.inorder(root)
    return iterator
}

func (this *BSTIterator) inorder(root *TreeNode) {
    if root == nil {
        return
    }
    this.inorder(root.Left)
    this.nodesSorted = append(this.nodesSorted, root.Val)
    this.inorder(root.Right)
}

func (this *BSTIterator) Next() int {
    this.index++
    return this.nodesSorted[this.index]
}

func (this *BSTIterator) HasNext() bool {
    return this.index+1 < len(this.nodesSorted)
}

func main() {
    root := &TreeNode{7, 
                &TreeNode{3, nil, nil}, 
                &TreeNode{15, 
                    &TreeNode{9, nil, nil}, 
                    &TreeNode{20, nil, nil}}}
    iterator := Constructor(root)
    fmt.Println(iterator.Next())  
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next())  
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next())   
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next()) 
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next())  
    fmt.Println(iterator.HasNext()) 
}

Explanation

Algorithm

1️⃣

Инициализируйте пустой массив, который будет содержать узлы бинарного дерева поиска в отсортированном порядке.

2️⃣

Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево.

3️⃣

Когда у нас будут все узлы в массиве, нам просто нужен указатель или индекс в этом массиве для реализации двух функций

hasNext

. Всякий раз, когда вызывается

hasNext

, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции

мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции

, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора.

😎