新疆做网站app软件推广怎么做
以上算法题中一个比较好的实现思路就是利用栈来进行实现，以下方法三就是利用栈来进行实现的，思路很好，很简练。进行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();*/