Binary Search Tree相关题目思路

简单题目使用非递归的中序遍历 背好模版
还有一些题目需要模拟搜索target的过程，用栈记录这个过程，然后用iterature。

题目列表

Binary Search Tree Iterator

173 Binary Search Tree Iterator
230 Kth Smallest Element in a BST
98 Validate Binary Search Tree

Binary Search Tree性质找节点 加 Iterator

*270 Closest Binary Search Tree Value
*272 Closest Binary Search Tree Value II
*285 Inorder Successor in BST recursive/iterative: memorizePath/iterative: withoutMemorizePath
235 Lowest Common Ancestor of a Binary Search Tree

Binary Search Tree Iterator

173. Binary Search Tree Iterator

public class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        if(root==null)
            return;
        // stack = new Stack<>();
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
    }

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

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.peek();
        TreeNode current = node;
        if(node.right!=null){
            node = node.right;
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
        }else{
            node = stack.pop();
            while(!stack.isEmpty() && stack.peek().left!=node){
                node = stack.pop();
            }
        }
        return current.val;
    }
}

230. Kth Smallest Element in a BST

class Solution {
    //O(h+k)
    public int kthSmallest(TreeNode root, int k) {
        return recursion(root, k);
    }
    private int count;
    private int result = -1;
    public int recursion(TreeNode root, int k) {
        count = k;
        helper(root);
        return result;
    }
    public void helper(TreeNode root){
        if(root==null)
            return;
        helper(root.left);
        count--;
        if(count==0){
            result = root.val;
            return;
        }
        helper(root.right);
    }
    public int iterative(TreeNode root, int k) {
        if(root==null || k<=0)
            return -1;
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(k==1)
                return node.val;
            k--;
            if(node.right!=null){
                node = node.right;
                while(node!=null){
                    stack.push(node);
                    node = node.left;
                }
            }else{
                node = stack.pop();
                while(!stack.isEmpty() && stack.peek().left!=node)
                    node = stack.pop();
            }
        }
        return -1;
    }
}

follow up:二叉树经常被修改/多次调用这个操作

98. Validate Binary Search Tree

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        // write your code here
        if(root==null)
            return true;
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        TreeNode pre = null;
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            TreeNode current = node;
            if(pre!=null && pre.val>=current.val)
                return false;
            if(node.right!=null){
                node = node.right;
                while(node!=null){
                    stack.push(node);
                    node = node.left;
                }
            }else{
                node = stack.pop();
                while(!stack.isEmpty() && stack.peek().left!=node)
                    node = stack.pop();
            }
            pre = current;
        }
        return true;
    }
}

Binary Search Tree性质找节点 加 Iterator

270. Closest Binary Search Tree Value

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
public int closestValue(TreeNode root, double target) {
        int result = root.val;
        while(root!=null){
            if(root.val==target)
                return root.val;
            if(root.val<target){
                result = Math.abs(result-target)>Math.abs(root.val-target) ? root.val : result;
                root = root.right;
            }else{
                result = Math.abs(result-target)>Math.abs(root.val-target) ? root.val : result;
                root = root.left;
            }
        }
        return result;
    }
public int recursive1(TreeNode root, double target) {
        TreeNode closetNode = root;
        int result = root.val;
        while(closetNode!=null){
            if(closetNode.val == target)
                return closetNode.val;
            result = Math.abs(result-target) > Math.abs(closetNode.val-target) ? closetNode.val : result;
            closetNode = closetNode.val>target ? closetNode.left : closetNode.right;
        }
        return result;
    }
    public int recursive2(TreeNode root, double target) {
        // write your code here
        TreeNode lower = findLower(root, target);
        TreeNode upper = findUpper(root, target);
        if(lower == null)
            return upper.val;
        if(upper == null)
            return lower.val;
        if(target-lower.val > upper.val-target)
            return upper.val;
        return lower.val;
    }
    private TreeNode findLower(TreeNode node, double target){
        if(node == null)
            return null;
        // 因为是找严格小于target的点 所以大于等于target节点 全部向左找
        if(node.val >= target)
            return findLower(node.left, target);
        // 当前节点小于target时 要继续看是不是有小于target而且更加接近target的节点 所以继续向右找 但是有可能右边都是大于target的了 所以要记录当前节点
        TreeNode current = findLower(node.right, target);
        if(current != null)
            return current;
        return node;
    }
    private TreeNode findUpper(TreeNode node, double target){
        if(node == null)
            return null;
        // 找大于等于target的第一个节点
        // 因为是找严格大于等于target的点 所以只有小于target节点 全部向才会向右右找
        if(node.val < target)
            return findUpper(node.right, target);
        // 如果是等于 相当于也存下来了如果左边有相等 那么左边的相等更接近起点 所以应该保留
        TreeNode current =  findUpper(node.left, target);
        if(current != null)
            return current;
        return node;
    }
}

272. Closest Binary Search Tree Value II

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> lowerStack = findLower(root, target);
        Stack<TreeNode> higherStack = new Stack<>();
        higherStack.addAll(lowerStack);
        if(!lowerStack.isEmpty() && lowerStack.peek().val>=target){
            findLower(lowerStack);
        }
        if(!higherStack.isEmpty() && higherStack.peek().val<target){
            findHigher(higherStack);
        }
        int count = 0;
        while(count<k && !lowerStack.isEmpty() && !higherStack.isEmpty()){
            if(target-lowerStack.peek().val > higherStack.peek().val-target){
                result.add(findHigher(higherStack));
            }else{
                result.add(findLower(lowerStack));
            }
            count++;
        }
        while(count<k && !lowerStack.isEmpty()){
            result.add(findLower(lowerStack));
            count++;
        }
        while(count<k && !higherStack.isEmpty()){
            result.add(findHigher(higherStack));
            count++;
        }
        return result;
        
    }
    private int findHigher(Stack<TreeNode> stack){
        TreeNode node = stack.peek();
        TreeNode current = node;
        if(node.right!=null){
            node = node.right;
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
        }else{
            node = stack.pop();
            while(!stack.isEmpty() && stack.peek().left!=node)
                node = stack.pop();
        }
        return current.val;
    }
    private int findLower(Stack<TreeNode> stack){
        TreeNode node = stack.peek();
        TreeNode current = node;
        if(node.left!=null){
            node = node.left;
            while(node!=null){
                stack.push(node);
                node = node.right;
            }
        }else{
            node = stack.pop();
            while(!stack.isEmpty() && stack.peek().right!=node)
                node = stack.pop();
        }
        return current.val;
    }
    private Stack<TreeNode> findLower(TreeNode root, double target){
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null){
            stack.push(root);
            if(root.val>=target){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return stack;
    }
}

285. Inorder Successor in BST

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // return withoutMemorizePath(root, p);
        return memorizePath(root, p);
        return recursive(root, p);
    }
    public TreeNode withoutMemorizePath(TreeNode root, TreeNode p) {
        // write your code here
        if(root==null || p==null)
            return null;
        TreeNode pre = null;
        while(root!=null){
            if(p.val < root.val){
                pre = root;
                root = root.left;
            }
            else if(p.val > root.val)
                root = root.right;
            else{
                if(root.right==null)
                    return pre;
                root = root.right;
                TreeNode result = root;
                while(root!=null){
                    result = root;
                    root = root.left;
                }
                return result;
            }
        }
        return null;
    }
    public TreeNode memorizePath(TreeNode root, TreeNode p) {
        // write your code here
        if(root==null || p==null)
            return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(stack.peek()!=p){
            TreeNode node = stack.peek();
            if(node.val < p.val){
                stack.push(node.right);
            }else{
                stack.push(node.left);
            }
        }
        TreeNode node = stack.peek();
        if(node.right!=null){
            node = node.right;
            while(node!=null){
                stack.push(node);
                node = node.left; 
            }
        }else{
            node = stack.pop();
            while(!stack.isEmpty() && stack.peek().left!=node)
                node = stack.pop();
        }
        if(stack.isEmpty())
            return null;
        return stack.peek();
    }
public TreeNode recursive(TreeNode root, TreeNode p) {
        // write your code here
        if (root == null || p == 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;
        }
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // return recursive(root, p, q);
        return nonrecursive(root, p, q);
    }
    public TreeNode recursive(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val<p.val && root.val<q.val)
            return recursive(root.right, p, q);
        else if(root.val>p.val && root.val>q.val)
            return recursive(root.left, p, q);
        else
            return root;
    }
    public TreeNode nonrecursive(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val<p.val && root.val<q.val)
                root = root.right;
            else if(root.val>p.val && root.val>q.val)
                root = root.left;
            else
                return root;
        }
        return null;
    }
}