Lowest Common Ancestor of a Binary Search Tree leetcode

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

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

二叉查找树 总结

Validate Binary Search Tree 利用中序遍历， 比较之前遍历的是否比当前点小， 如果小就返回true 否则false

Recover Binary Search Tree 同样利用中序遍历， 比较之前的点和当前的点， 把逆序的node存储 最后对换

Unique Binary Search Trees
Unique Binary Search Trees II

Search Range in Binary Search Tree

复习完动归和递归再写这两道题

Recover Binary Search Tree leetcode

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

这道题是要求恢复一颗有两个元素调换错了的二叉查找树。中序遍历BST 然后找到逆序。
1. 中序遍历相邻的两个元素被调换了，很容易想到就只需会出现一次违反情况，只需要把这个两个节点记录下来最后调换值就可以；
2. 如果是不相邻的两个元素被调换了，会发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。比如1234567,1和5调换了，会得到5234167，逆序发生在52和41，我们需要把4和1调过来，那么就是52的第一个元素，41的第二个元素调换即可。
时间复杂度是O(n)，空间是栈大小O(logn)

public class Solution {
    TreeNode pre, first, second;
    public void recoverTree(TreeNode root) {
        pre = null;
        first = null;
        second = null;
        inorder(root);
        if (first != null && second != null){
            int tem = first.val;//只调换val 不是node
            first.val = second.val;
            second.val = tem;
        }
    }
    private void inorder(TreeNode root){
        if (root == null){
            return;
        }
        inorder(root.left);
        if (pre == null){
            pre = root;//初始化pre
        } else {
            if (pre.val > root.val){
                if (first == null){
                    first = pre;//第一个逆序点
                } 
                second = root;//如果相邻第一次就找全， 如果不相邻则遍历完后找到第二个逆序点
            }
            pre = root;//给pre赋值
        }
        inorder(root.right);
    }
}

//方法2 不用全局变量

public class Solution {
    public void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        ArrayList<TreeNode> tem = new ArrayList<TreeNode>();
        tem.add(null);
        helper(root, res, tem);
        if (res.size() > 0) {
            int save = res.get(0).val;
            res.get(0).val = res.get(1).val;
            res.get(1).val = save;
        }
        
    }
    public void helper(TreeNode root, ArrayList<TreeNode> res, ArrayList<TreeNode> tem) {
        if (root == null) {
            return;
        }
        helper(root.left, res, tem);
        if (tem.get(0) != null && root.val < tem.get(0).val) {
            if (res.size() == 0) {
                res.add(tem.get(0));
                res.add(root);
            } else {
                res.set(1, root);
            }
        }
        tem.set(0, root);
        helper(root.right, res, tem);
    }
}

Binary Search Tree Iterator leetcode

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.

这道题相当于用stack来实现递归的中序遍历。不能递归的都用stack来实现

每个next都相当于返回当前root的子树的最小结点， 所以一直向左找到最小点返回， 下一个点是当前点的右子树（已经没有左子树了）

判定时候的cur！= null是保证判定root点时候

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    private TreeNode cur;
    public BSTIterator(TreeNode root) {
        cur = root;
    }

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

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

Search Range in Binary Search Tree

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Example

For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

          20

       /        \

    8           22

  /     \

4       12

1. 如果root.val > k1 递归的找他的左子树

2. 如果root.val 在k1, k2之间 添加root到result

3. 如果root.val < k2 递归找他的右子树

public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        helper(root, k1, k2, result);
        return result;
    }
    private void helper(TreeNode root, int k1, int k2, ArrayList<Integer> result){
        if (root == null){
            return;
        }
        if (root.val > k1){
            helper(root.left, k1, k2, result);
        }
        if (root.val >= k1 && root.val <= k2){
            result.add(root.val);
        }
        if (root. val < k2){
            helper(root.right, k1, k2, result);
        }
    }
}

Validate Binary Search Tree leetcode

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

bfs中序遍历整个树， 因为BST所以是递增的 

根据这一点我们只需要中序遍历这棵树，然后保存前驱结点，每次检测是否满足递增关系即可。注意以下代码我么用一个一个变量的数组去保存前驱结点，原因是java没有传引用的概念，如果传入一个变量，它是按值传递的，所以是一个备份的变量，改变它的值并不能影响它在函数外部的值，算是java中的一个小细节。

一次树的遍历，所以时间复杂度是O(n)，空间复杂度是O(logn)。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(null);
        return helper(root, res);
    }
    public boolean helper(TreeNode root, ArrayList<Integer> res){
        if (root == null){
            return true;
        }
        boolean left = helper(root.left, res);
        if (res.get(0) != null && res.get(0) >= root.val){//显示left和root比， 存入root， 然后root和right比 存入right
            return false;
        }
        res.set(0, root.val);
        boolean right = helper(root.right, res);
        return left && right;
    }
}