98. Validate Binary Search Tree
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.
Example 1:
2
/ \
1 3
Input: [2,1,3] Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null)
return true;
return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
boolean dfs(TreeNode root,long min,long max){
if(root==null)
return true;
if(root.val<=min||root.val>=max)
return false;
return dfs(root.left,min,(int)root.val)&&dfs(root.right,(int)root.val,max);
}
}- 如果根结点==null，直接返回true
- 如果根节点小于min或者大于max，返回false
- 如果根结点小于min或者小于左节点，返回false
- 如果根结点小于右节点或者大于max，返回false
堆排序
public class Sort {
public static void main(String[] args) {
Sort sort = new Sort();
System.out.println("sort:");
int[] a = new int[]{1, 8, 2, 9, 6, 7, 5, 0, 4, 3};
sort.heapSort(a);
System.out.println(Arrays.toString(a));
}
private void heapSort(int[] a) {
for (int i = (a.length - 2) / 2; i >= 0; i--) {
// 调整一个最大堆，让第一个根结点的值最大
adjustHeap(a, i, a.length);
}
for (int i = a.length - 1; i >= 0; i--) {
// 将根结点的最大值移动到最后一位
int temp = a[i];
a[i] = a[0];
a[0] = temp;
adjustHeap(a, 0, i);
}
}
// 目的是下移根节点，让最大的节点在根结点的位置，让大的节点往根结点移动
private void adjustHeap(int[] a, int parentIndex, int length) {
// 首先保存下根结点
int temp = a[parentIndex];
// 计算左侧子节点的坐标
int childIndex = 2 * parentIndex;
// 如果子节点坐标没有越界
while (childIndex < length) {
// 如果右侧节点存在，且比左侧节点大
if (childIndex + 1 < length && a[childIndex] < a[childIndex + 1]) {
// 移动到右侧节点坐标
childIndex++;
}
// 如果根结点比子节点还要大，直接break，后面的不用继续比较
if (temp >= a[childIndex]) {
break;
}
// 如果根结点比子节点小，那么将子节点的值赋值给根结点
a[parentIndex] = a[childIndex];
// 父节点的坐标赋值为子节点坐标
parentIndex = childIndex;
// 子节点坐标继续*2计算
childIndex = 2 * parentIndex;
}
// 最后的子节点赋值为根节点
a[parentIndex] = temp;
}
}