leetcode 173. Binary Search Tree Iterator 二叉树中序遍历非递归

阳光穿透心脏的1/2处 2022-06-08 08:18 157阅读 0赞

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

本题的意思就是按照中序遍历访问元素，注意寻找第二大的元素。

代码如下：

import java.util.Stack;
    
    /*class TreeNode 
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    /*
     * 这个问题的关键就是返回第二小的结点
     * 
     * */
    public class BSTIterator 
    {
        
        /*
         * stack保存的是最小的结点，本质就是按照中序遍历的
         * */
        public Stack<TreeNode> stack=new Stack<>();
        public BSTIterator(TreeNode root) 
        {
            while(root!=null)
            {
                stack.push(root);
                root = root.left;
            }
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() 
        {
            if(stack.size()<=0)
                return false;
            else
                return true;
        }
    
    
        /*
         * 返回对应的值并计算下一个结点的位置
         * */
        /** @return the next smallest number */
        public int next() 
        {
           TreeNode one=stack.pop();
           int res=one.val;
           if(one.right!=null)
           {
               one=one.right;
               while(one!=null)
               {
                    stack.push(one);
                    one = one.left;
               }
           }
           return res;
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */