网站模板修改教程,网站建设 外文文献,网站群建设需求,长春网站推广网诚传媒以上算法题中一个比较好的实现思路就是利用栈来进行实现#xff0c;以下方法三就是利用栈来进行实现的#xff0c;思路很好#xff0c;很简练。进行next的时候#xff0c;先是一直拿到左边的子树#xff0c;直到null为止#xff0c;这一步比较好思考一点#xff0c;下一… 以上算法题中一个比较好的实现思路就是利用栈来进行实现以下方法三就是利用栈来进行实现的思路很好很简练。进行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 DequeTreeNode 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 {
// ListTreeNode 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();*/
