CONY的世界

173. Binary Search Tree Iterator

這題題意有點模糊，一開始我作成preorder sort 還過了 

但是後來看了大家的討論，才發現是要給從小排到大

所以就重寫了一遍，而且注意題目要求是 average O(1) time 和 O(h) space

所以不可以把left subtree整個塞進去...不然會變成O(N/2) space

所以作法是先塞最左邊的node （O(h) space) ，然後遇到有right node 實在整個right subtree塞進stack裡面 (也是O(h) space)

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {

    Stack<TreeNode> stack = new Stack();
    public BSTIterator(TreeNode root) {
        if(root != null)    
            putAllLeftNode(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.empty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        if(node.right != null)  putAllLeftNode(node.right);
        return node.val;
    }
    public void putAllLeftNode(TreeNode n){
        for(TreeNode node = n; node != null; node = node.left)
            stack.push(node);
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

 285. Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

塞最一開始用了上課學到的方式考慮

基本上BST successor有兩種情形

1. 從右邊最小的child 

2. 如果沒有右邊的child 往上找，第一個是他的左邊child 的 node

第2種情形因為需要往上找，所以用個stack來記錄走過的路線，然後一個一個pop出來判斷是不是左邊的child

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null) {
            if(cur == p) {
                TreeNode prev;
                if(cur.right != null){ 
                    prev = cur.right;
                    while(prev.left != null)
                        prev = prev.left;
                } else{
                    prev = (stack.empty())?null:stack.pop();
                    while(prev != null && cur != prev.left) {
                        cur=prev;
                        prev = (stack.empty())?null:stack.pop();
                    }
                }               
                return prev;
            } else {
                stack.push(cur);
                if(cur.val > p.val)   cur = cur.left;
                else cur = cur.right;
            }             
        }
        return null;
    }
}

看討論後，有人是用recursion更簡潔漂亮，用到題目給的 p node必定存在 
然後搭配上因為要找successor，所以這邊是假設即使是right node 也要判斷他有沒有left child  node 的情形
所以最後做決定都會在left node 上，有存在left node就是left node，沒有的話就是自己本身

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null)    return null;
        
        if(root.val <= p.val){
            return inorderSuccessor(root.right, p);   
        }else{
            TreeNode left = inorderSuccessor(root.left, p);
            return (left!=null)?left:root;
        }        
    }
}