当前位置：首页 > news >正文

leetcode 173.二叉搜索树迭代器栈绝妙思路

news 2025/7/18 13:56:56

在这里插入图片描述
以上算法题中一个比较好的实现思路就是利用栈来进行实现，以下方法三就是利用栈来进行实现的，思路很好，很简练。进行next的时候，先是一直拿到左边的子树，直到null为止，这一步比较好思考一点，下一步，弹出时，只修改cur节点即可，总之要明白while循环中cur变量代表什么含义，在循环结束时可以为cur更好的赋值。此处的cur就代表传入一个节点，就可以根据这个节点为根实现中序遍历。因此，当进行右子树时，直接将这个右子树赋值给cur即可进行下一轮次的循环。所以，在利用while循环时，要注重循环变量代表什么含义才能够更好的写出优雅的算法来。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 方法三，利用栈来进行模拟
class BSTIterator {private TreeNode cur;private Deque<TreeNode> stack;  // 双向队列，可以模拟栈public BSTIterator(TreeNode root) {this.cur = root;this.stack = new LinkedList();}public int next() {// 以下利用栈思路很好while(cur != null){stack.push(cur);cur = cur.left;}TreeNode node = stack.pop();cur = node.right;return node.val;}public boolean hasNext() {return cur != null || !stack.isEmpty();}
}// 方法二：提前遍历
// class BSTIterator {
//     List<TreeNode> lists = new LinkedList();
//     private int index = 0;//     public BSTIterator(TreeNode root) {
//         preOrder(root);
//     }//     public int next() {
//         return lists.get(index++).val;
//     }//     public boolean hasNext() {
//         return index < lists.size();
//     }//     public void preOrder(TreeNode root){
//         if(root != null){
//             preOrder(root.left);
//             lists.add(root);
//             preOrder(root.right);
//         }
//     }// }// 方法一：难点是如何让root 移动到下一个结点处
// class BSTIterator {
//     private TreeNode root;//     public BSTIterator(TreeNode root) {
//         this.root = root;
//     }//     public int next() {
//         int value = root.val;
//         // root 移动到下一个结点处
//         return value;
//     }//     public boolean hasNext() {
//         return root != null;
//     }
// }/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj = new BSTIterator(root);* int param_1 = obj.next();* boolean param_2 = obj.hasNext();*/