golang 解法, 执行用时: 220 ms, 内存消耗: 30.3 MB, 提交时间: 2023-10-22 08:37:10

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
	parent     []*TreeNode
	cache      []*TreeNode
	next       *TreeNode
	cacheIndex int
}

func Constructor(root *TreeNode) BSTIterator {
	return BSTIterator{
		parent:     nil,
		cache:      nil,
		next:       &TreeNode{Val: -1, Right: root},
		cacheIndex: -1,
	}
}

func (i *BSTIterator) HasNext() bool {
	return i.cacheIndex < len(i.cache)-1 || len(i.parent) > 0 || i.next.Right != nil
}

func (i *BSTIterator) Next() int {
	if i.cacheIndex < len(i.cache)-1 {
		i.cacheIndex++
		return i.cache[i.cacheIndex].Val
	}
	i.next = i.next.Right
	for i.next != nil {
		i.parent = append(i.parent, i.next)
		i.next = i.next.Left
	}
	i.next = i.parent[len(i.parent)-1]
	i.parent = i.parent[:len(i.parent)-1]
	i.cache = append(i.cache, i.next)
	i.cacheIndex++
	ans := i.next.Val
	return ans
}

func (i *BSTIterator) HasPrev() bool {
	return i.cacheIndex > 0
}

func (i *BSTIterator) Prev() int {
	i.cacheIndex--
	return i.cache[i.cacheIndex].Val
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.HasNext();
 * param_2 := obj.Next();
 * param_3 := obj.HasPrev();
 * param_4 := obj.Prev();
 */

java 解法, 执行用时: 71 ms, 内存消耗: 71.8 MB, 提交时间: 2023-10-22 08:36:01

/**
 * 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 {

   List<Integer> arr = new ArrayList();
   int pointer;
   int n;
   
   public void inorder(TreeNode r, List<Integer> arr) {
       if (r == null) return;
       inorder(r.left, arr);
       arr.add(r.val);
       inorder(r.right, arr);
   }

   public BSTIterator(TreeNode root) {
       inorder(root, arr);
       n = arr.size();
       pointer = -1;
   }
   
   public boolean hasNext() {
       return pointer < n - 1;
   }
   
   public int next() {
       ++pointer;
       return arr.get(pointer);
   }
   
   public boolean hasPrev() {
       return pointer > 0;
   }
   
   public int prev() {
       --pointer;
       return arr.get(pointer);
   }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * boolean param_1 = obj.hasNext();
 * int param_2 = obj.next();
 * boolean param_3 = obj.hasPrev();
 * int param_4 = obj.prev();
 */

java 解法, 执行用时: 69 ms, 内存消耗: 64 MB, 提交时间: 2023-10-22 08:35:24

/**
 * 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 {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode dummy = new TreeNode(-1);
    TreeNode cur = dummy;  // 游标初始位置必须是第一个元素之前的位置。
    
    public BSTIterator(TreeNode root) {
        leftMost(root);   // root的左侧节点全部入栈
    }

    // 游标后面有（中序遍历序列的）节点，或者栈非空（游标节点有父节点），就有下一个元素
    public boolean hasNext() {
        return cur.right != null || !stack.isEmpty();  
    }
    
    public int next() {
        // 游标后面没有（中序遍历序列的）节点了，回到上一层节点去找"下一个元素"。比如父节点的右孩子的左孩子，就可以是中序遍历的下一个元素
        if (cur.right == null) {   
            TreeNode next = stack.pop();
            
            leftMost(next.right);  // 上一层节点的左子孙
            next.right = null; 
            
            
            next.left = cur;  // next是游标cur的下一个中序遍历节点，把它们像"list"一样连接起来。
            cur.right = next;
        }
        cur = cur.right;     // 右移游标
        return cur.val;
    }
    
    public boolean hasPrev() {
        return cur != dummy && cur.left != dummy;
    }
    
    public int prev() {
        cur = cur.left;  // 左移游标
        return cur.val; 
    }
    private void leftMost(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * boolean param_1 = obj.hasNext();
 * int param_2 = obj.next();
 * boolean param_3 = obj.hasPrev();
 * int param_4 = obj.prev();
 */

python3 解法, 执行用时: 388 ms, 内存消耗: 46.1 MB, 提交时间: 2023-10-22 08:34:46

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        def dfs_LNR(rt: TreeNode) -> None:
            if rt:
                dfs_LNR(rt.left)
                self.nums.append(rt.val)
                dfs_LNR(rt.right)
        self.nums = []
        dfs_LNR(root)
        self.n = len(self.nums)
        self.i = 0

    def hasNext(self) -> bool:
        return self.i < self.n
    #--------------- 初始化内部指针的是个不存在的最小值？？self.i往左平移l了1位
    def next(self) -> int:
        self.i += 1
        return self.nums[self.i - 1]
    #-------------- 神奇的很，不知道是什么意思？？？？？self.i往左平移了1位
    def hasPrev(self) -> bool:
        return 1 < self.i

    def prev(self) -> int:
        self.i -= 1
        return self.nums[self.i - 1]


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()

python3 解法, 执行用时: 380 ms, 内存消耗: 51.5 MB, 提交时间: 2023-10-22 08:34:37

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stk = []
        p = root
        while p:
            self.stk.append(p)
            p = p.left

        self.nums = []
        self.i = 0          #虚指！！！！！！！！！！！

    def hasNext(self) -> bool:
        if self.i == len(self.nums) and self.stk == []:
            return False
        return True

    def next(self) -> int:
        if self.i <= len(self.nums) - 1 :
            self.i += 1
            return self.nums[self.i - 1]

        cur = self.stk.pop(-1)
        self.nums.append(cur.val)        

        p = cur.right
        while p:
            self.stk.append(p)
            p = p.left

        self.i += 1
        #return self.nums[self.i - 1]
        return cur.val

    def hasPrev(self) -> bool:
        return 2 <= self.i      #至少是第2个（从1开始数）

    def prev(self) -> int:
        self.i -= 1
        return self.nums[self.i - 1]


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()

cpp 解法, 执行用时: 256 ms, 内存消耗: 146.7 MB, 提交时间: 2023-10-22 08:34:23

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class BSTIterator {
public:
    stack<TreeNode *> stk;
    vector<int> nums;
    int i;      //虚指！！！！！！！！！！！！！！
    
    BSTIterator(TreeNode* root) {
        TreeNode * p = root;
        while (p)
        {
            stk.push(p);
            p = p->left;
        }

        this->i = 0;
    }
    
    bool hasNext() {
        if (i == nums.size() && stk.size() == 0)
            return false;
        return true;
    }
    
    int next() {
        if (i < nums.size())
        {
            i ++;
            return nums[i - 1];
        }

        TreeNode * cur = stk.top();     stk.pop();
        nums.push_back(cur->val);

        TreeNode * p = cur->right;
        while (p)
        {
            stk.push(p);
            p = p->left;
        }

        i ++;
        //return cur->val;
        return nums[i - 1];
        
    }
    
    bool hasPrev() 
    {
        return 2 <= i;
    }
    
    int prev() 
    {
        i --;
        return nums[i - 1];
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * bool param_1 = obj->hasNext();
 * int param_2 = obj->next();
 * bool param_3 = obj->hasPrev();
 * int param_4 = obj->prev();
 */

cpp 解法, 执行用时: 292 ms, 内存消耗: 147.9 MB, 提交时间: 2023-10-22 08:33:58

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class BSTIterator {
public:
    vector<int> nums;
    int n;
    int i;

    BSTIterator(TreeNode* root) {
        dfs_LNR(root);
        this->n = nums.size();
        this->i = 0;
    }
    
    bool hasNext() 
    {
        return i < n;
    }
    //----------- 所以的i左移了1位
    int next() 
    {
        i ++;
        return nums[i - 1];
    }
    
    bool hasPrev() 
    {
        return 2 <= i;
    }
    
    int prev() 
    {
        i --;
        return nums[i - 1];
    }
    //--------- 中序遍历 ----------//
    void dfs_LNR(TreeNode* rt) {
        if (rt)
        {
            dfs_LNR(rt->left);
            nums.push_back(rt->val);
            dfs_LNR(rt->right);
        }
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * bool param_1 = obj->hasNext();
 * int param_2 = obj->next();
 * bool param_3 = obj->hasPrev();
 * int param_4 = obj->prev();
 */