Flatterning the BST, Using O(1) space, O(1) for both hasNext() and next()


  • 0
    X

    We are not asked to maintain tree structure are we?

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class BSTIterator {
        private TreeNode head;
        private TreeNode pre;
        public BSTIterator(TreeNode root) {
                convert(root);
        }
        
        private void convert(TreeNode root) {
            if (root == null) {
                return;
            }
            if (root.left != null){
                convert(root.left);
            }
            if (head == null) {
                head = root;
            }
            if (pre == null) {
                pre = root;
            } else {
                pre.right = root;
                pre = root;
            }
            if (root.right != null) {
                convert(root.right);
            }
            
        }
         
    
       public boolean hasNext() {
            return head != null;
        }
        
        public int next() {
            if (hasNext()) {
                       TreeNode t = head;
            head = head.right;
            return t.val; 
            } else {
                return -1;
            }
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */

  • 0
    S

    The memory of your code is o(n)?,can it be accepted?


  • 0
    X

    no additional nodes created, so it is o1. passed tests


  • 0
    B
    This post is deleted!

  • 0
    C

    It is not a good solution because you should never change the tree while you iterate it.


  • 0
    G

    Cannot compile. "Line 38: error: illegal start of expression" -- got this after copy paste and submit.


  • 0
    X

    arguably agree. Whether to maintain a tree structure totally depends on how the tree is going to be used. There is not a definite answer to be good or bad. Depends on the context which is missing in the requirement.


  • 0
    X

    Surprisingly I reran the test and it passed my oj. Sorry for the confusion. Not sure what happened.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.