二叉查找树
什么是二叉查找树？它其实是二叉树的一种比较特别的方式：
- 左子树上的一切节点的值均小于其根节点的值；
- 右子树上的一切节点的值均大于其根节点的值；
- 准确的说，其左右子树均为二叉查找树。
那么二叉查找树有什么特性呢?
其中序遍历的集合，为升序排序。这个特性非常重要，能够帮咱们处理很多复杂的问题。
问题1：求二叉查找树中不同节点之间绝对差最小
其实假如了解二叉查找树的特性，进行一次中序遍历，由于是升序排序，因而期间不断比较两个相邻节点之间的差值，就能够找到对应的最小差值。
public int getMinimumDifference(TreeNode head) {
Stack<TreeNode> stack = new Stack();
int abs = Integer.MAX_VALUE;
int pre = -1;
while(!stack.isEmpty() || head != null){
if(head != null){
stack.push(head);
head = head.left;
}else{
//弹出节点
TreeNode node = stack.pop();
if(pre < 0){
pre = node.val;
}else{
if( Math.abs(node.val - pre) < abs){
abs = Math.abs(node.val - pre);
}
pre = node.val;
}
head = node.right;
}
}
return abs;
}
问题2：求查找二叉树中第k小的节点
其实这道题也很简单，便是在节点弹出的时候，记录一个pos，假如pos等于k，那么就直接回来即可；咱们不需求关心k是否超出二叉树的节点总数，while循环完毕之后还没完结匹配，直接回来0即可。
public int kthSmallest(TreeNode root, int k) {
if(root == null){
return 0;
}
Stack<TreeNode> stack = new Stack();
int pos = 0;
while(!stack.isEmpty() || root != null){
if(root != null){
stack.push(root);
root = root.left;
}else{
//开端弹出
TreeNode node = stack.pop();
pos ;
if(pos == k){
return node.val;
}
root = node.right;
}
}
return 0;
}
逆向思想验证二叉树是否为二叉查找树
由于中序遍历，一切的节点是升序的，因而每次弹出节点都与上次节点做一次比较，假如不是递增的话，留意节点值不能相等， 那么就认为不是二叉查找树。
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
Stack<TreeNode> stack = new Stack();
Integer pre = null;
while(!stack.isEmpty() || root != null){
if(root != null){
stack.push(root);
root = root.left;
}else{
TreeNode node = stack.pop();
if(pre == null){
pre = node.val;
}else{
if(node.val <= pre){
return false;
}
pre = node.val;
}
root = node.right;
}
}
return true;
}
依据前序、中序、后序数组构建二叉树
关于经过数组构建二叉树的问题，大致分为两种：
- 经过前序和中序数组构建二叉树，或许经过后序和中序数组构建二叉树；
- 经过数组构建平衡二叉查找树。
想一个问题，为啥必定需求中序数组，经过前序和后序无法构建吗？是的，其实前序和后序更多的是起辅佐作用，意图便是为了找到根节点在中序数组中的方位， 从而经过迭代的方式构建二叉树。
标题
给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请结构二叉树并回来其根节点。
解题思路
给定了先序遍历，咱们知道其顺序为头左右，所以根节点便是前序数组第一个元素，那么如何知道中序遍历中头结点的方位呢？咱们能够经过哈希表来存储对应的节点和方位的映射关系。
private Map<Integer,Integer> map = new HashMap<>();
/**
* 依据前序数组和中序数组构建二叉树
* @param preorder 前序数组
* @param inorder 中序数组
* @return 二叉树
*/
public TreeNode buildTree(int[] preorder, int[] inorder){
//有一个为空，就没法构建
if(preorder == null || inorder == null){
return null;
}
//存储中序数组的val和其方位的映射
for (int i = 0;i<inorder.length;i ){
map.put(inorder[i],i);
}
//开端构建二叉树
return buildInner(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}
/**
* 内部构建二叉树
* @param preorder 前序数组
* @param inorder 中序数组
* @param ps 前序数组的开始方位
* @param pe 前序数组的终点方位
* @param is 后序数组的开始方位
* @param ie 后序数组的终点方位
*/
private TreeNode buildInner(int[] preorder,int[] inorder,int ps,int pe,int is,int ie){
if(ps > pe || is > ie){
return null;
}
//找到根节点
int rootVal = preorder[ps];
//在中序数组中的方位
int index = map.get(rootVal);
//左子树的长度
int leftChildLength = index-is;
TreeNode root = new TreeNode(rootVal);
//构建左子树
root.left = buildInner(preorder,inorder,ps 1,ps leftChildLength,is,is leftChildLength-1);
root.right = buildInner(preorder,inorder,ps leftChildLength 1,pe,index 1,ie);
return root;
}
在构建二叉树时，咱们只需求找到前序数组中左子树的方位和中序数组中左子树的方位以及前序数组中右子树的方位和中序数组中右子树的方位即可经过迭代完结。
标题
给你一个整数数组nums，其中元素现已按升序排列，请你将其转换为一棵高度平衡二叉查找树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
解题思路
这道题构建的二叉树不是固定的，任意二叉树均能够，可是需求构建一棵平衡二叉查找树，依据咱们前面介绍二叉查找树的特性，标题中给到的是一个升序数组，那么这个数组便是这棵树的中序遍历数组。一起又要保持平衡，因而只需求将数组一分为2，左半部分构建左树，右半部分构建右树，中心的数字即为这棵二叉树的根节点。
public TreeNode sortedArrayToBST(int[] nums) {
//平衡二叉查找树，即高度差不能超过1，因而找到数组的中心元素，作为根节点，
//然后左右构建二叉树
return buildTree(nums,0,nums.length-1);
}
private TreeNode buildTree(int nums[],int start,int end){
if(start > end){
return null;
}
int middle = (end start) / 2;
TreeNode root = new TreeNode(nums[middle]);
root.left = buildTree(nums,start,middle-1);
root.right = buildTree(nums,middle 1,end);
return root;
}
