Leetcode BST系列（一）

BST定义

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2.若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3.任意节点的左、右子树也分别为二叉查找树；
4.没有键值相等的节点。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(log n) 。
二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

653. Two Sum IV - Input is a BST

从这一题开始的原因是LeetCode第一题就是两数之和，以前做653这个题目的思路就是把遍历到的每一个节点的值放到set中，然后再判断当前节点值与目标值的差是否在set中，这样解题是可行的。但是第一题的两数之和有一个解法就是把数组排序然后两端逼近，然后就想到了BST也是可以通过中序遍历转成一个有序的数组，那么再两头逼近又可以求解了。所以我又提交了一遍新的解法，上面显示速度还比我一年前提交的快。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int n = list.size()-1;
        for(int i=0, j=n; i<j;){
            if(list.get(i) + list.get(j) > k) {
                j--;
            } else if (list.get(i) + list.get(j) < k) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }
    // 中序遍历
    public void inorder(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

783. Minimum Distance Between BST Nodes && 530. Minimum Absolute Difference in BST

在讨论区有人说这两题代码提交一样的，所以我也放到一起。题意是找出BST中任意两个节点相差最小的值。
很明显还是要用到BST中序遍历时是从小到大的性质，那么只需要比较任意相邻两个节点相减的值，第一遍提交我是直接把上面代码复制过去改了for循环的逻辑。

int n = list.size();
int min = Integer.MAX_VALUE;
for(int i=0; i<n-1; i++) {
    int t = list.get(i+1) - list.get(i);
    if(t < min) {
        min = t;
    }
}

其实放到list中是多余的，因为中序遍历的时候可以直接计算相邻两个节点的差值，所以直接把计算放到中序遍历的时候处理。

class Solution {

	private Integer min = Integer.MAX_VALUE;
	private Integer pre = null;

    public int minDiffInBST(TreeNode root) {
       	if(root == null) {
       		return min;
       	}
        
        minDiffInBST(root.left);
        if(pre != null) {
			min = Math.min(min, root.val - pre);        	
        }
        pre = root.val;  //保存节点值
        minDiffInBST(root.right);
        return min;
    }
}