二进制搜索树迭代器Java [英] Binary Search Tree Iterator java

问题描述

我做了LeetCode问题二进制搜索树迭代器.以下代码是我从他人那里学到的.我不明白哪一部分是cur = cur.right.因为我得到的cur.val值最小.为什么我需要将cur.right分配给cur?当我删除cur = cur.right时，它说超过了时间限制.有人可以帮我解释一下吗?

 公共类BSTIterator {堆栈< TreeNode>堆;TreeNode cur;公共BSTIterator(TreeNode根目录){stack =新的Stack<>();cur =根；}/** @返回下一个最小数字*/public int next(){while(cur！= null){stack.push(cur);cur = cur.left;}cur = stack.pop();int val = cur.val;cur = cur.right;//为什么需要将cur.right分配给cur?返回值}} 

解决方案

我提交了代码，成功了. https://leetcode.com/problems/binary-search-tree-iterator/

您可以在这里找到它. https://github.com/yan-khonski-it/bst/blob/master/bst-core/src/main/java/com/yk/training/bst/iterators/BSTIterator.java

说明.您必须使用 inorder ，该方法首先访问左子树，然后访问当前节点，然后访问右子树，以便您按升序遍历所有元素.

现在，您有了堆栈，其中包含应按正确顺序在 next 调用中返回的所有节点.

next 将删除堆栈中的最后一个元素.现在，您检查当前节点(如果它具有正确的子树).如果是这样，则需要遍历右侧子树的左侧元素.

 /***在{@link #next()}中查找要返回的下一个节点.*将其推入堆栈.*/公共无效navigationLeftSubtree(){stack.push(currentNode);while(currentNode.left！= null){currentNode = currentNode.left;stack.push(currentNode);}} 

在这种情况下，(当前节点存在右子树)，应将当前节点的右子节点放入堆栈中.如果您已经访问过电流，则不希望将其放入堆栈中.

  public int next(){currentNode = stack.pop();最后的int currentValue = currentNode.value;如果(currentNode.right！= null){//将右子树的根推入堆栈.currentNode = currentNode.right;navigationLeftSubtree();}返回currentValue;} 

I did the LeetCode question Binary Search Tree Iterator. the following code is what I learned from others. One part I didn't understand which is cur = cur.right. Since I got the smallest value of cur.val. Why do I need to assign cur.right to cur? When I remove cur = cur.right, it said time limit exceeded. Could someone can help me to explain it?

public class BSTIterator {
    Stack<TreeNode> stack;
    TreeNode cur;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        cur = root;
    }

    /** @return the next smallest number */
    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int val = cur.val;
        cur = cur.right;  //why needed to assign cur.right to cur? 
        return val;
    }
} 

解决方案

I submitted my code, it was successful. https://leetcode.com/problems/binary-search-tree-iterator/

You can find it here. https://github.com/yan-khonski-it/bst/blob/master/bst-core/src/main/java/com/yk/training/bst/iterators/BSTIterator.java

Explanation. You have to use inorder which first visits the left sub-tree, then visit the current node, and then the right sub-tree, so you will iterate through all the elements in the ascending order.

Now, you have stack, which holds all the node that you should return in next call in the correct order.

next will remove the last element from the stack. Now you check the current node, if it has right subtree. If so, you need to iterate though left elements of the right subtree.

   /**
     * Find next node to be returned in {@link #next()}.
     * Push it to stack.
     */
    public void navigateLeftSubtree() {
        stack.push(currentNode);

        while (currentNode.left != null) {
            currentNode = currentNode.left;
            stack.push(currentNode);
        }
    }

In this case, (right sub tree is present for current node), you should put the right child of the current node into the stack. You don't want to put the current into the stack, if you have already visited it.

    public int next() {
        currentNode = stack.pop();
        final int currentValue = currentNode.value;

        if (currentNode.right != null) {
            // Push root of the right subtree into stack.
            currentNode = currentNode.right;
            navigateLeftSubtree();
        }

        return currentValue;
    }

这篇关于二进制搜索树迭代器Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！