二进制搜索树迭代器Java

现在，您有了堆栈，其中包含应按正确顺序在 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.javaExplanation.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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！