关于java:LeetCode173二叉搜索树迭代器

42次阅读

共计 1842 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：实现一个二叉搜寻树迭代器类 BSTIterator，示意一个按中序遍历二叉搜寻树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。

boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true；否则返回 false。

int next()将指针向右挪动，而后返回指针处的数字。

留神，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你能够假如 next() 调用总是无效的，也就是说，当调用 next() 时，BST 的中序遍历中至多存在一个下一个数字。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：中序遍历

首先，在 BSTIterator 内申明一个 List 为 values 用来存二叉树的节点值，在构造方法内通过中序遍历的形式将节点值初始化到 values 中。

而后，申明一个 index 标识以后地位，next()办法和 hasNext() 办法的实现即依赖于 index 和 values 进行判断即可。

import com.kaesar.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeetCode_173 {public static void main(String[] args) {
        // 测试用例
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(3);
        root.right = new TreeNode(15);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(20);

        BSTIterator bSTIterator = new BSTIterator(root);
        System.out.println(bSTIterator.next());    // 返回 3
        System.out.println(bSTIterator.next());    // 返回 7
        System.out.println(bSTIterator.hasNext()); // 返回 True
        System.out.println(bSTIterator.next());    // 返回 9
        System.out.println(bSTIterator.hasNext()); // 返回 True
        System.out.println(bSTIterator.next());    // 返回 15
        System.out.println(bSTIterator.hasNext()); // 返回 True
        System.out.println(bSTIterator.next());    // 返回 20
        System.out.println(bSTIterator.hasNext()); // 返回 False
    }

}

class BSTIterator {
    private int index;
    private List<Integer> values;

    public BSTIterator(TreeNode root) {
        this.index = 0;
        this.values = new ArrayList<>();
        inOrder(root, values);
    }

    /**
     * 中序遍历
     *
     * @param root
     * @param values
     */
    private void inOrder(TreeNode root, List<Integer> values) {if (root == null) {return;}
        inOrder(root.left, values);
        values.add(root.val);
        inOrder(root.right, values);
    }

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

    public boolean hasNext() {return index < values.size();
    }
}