题目地址
https://leetcode-cn.com/problems/validate-binary-search-tree
题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
/**
* Created by zcdeng on 2021/2/1.
*/
public class VerifyBT {
public static void main(String[] args) {
int[] arr = {-2147483648};
TreeNode head = TreeNode.createTreeNode(arr);
boolean result = verifyBT(head, new ArrayList<Integer>());
System.out.println(result);
result = verifyBTV2(head, new long[] {Long.MIN_VALUE});
System.out.println(result);
result = verifyBTV3(head, Long.MIN_VALUE, Long.MAX_VALUE);
System.out.println(result);
}
/**
* 二叉搜索树的中序遍历是递增序列
* 运行时间 1 ms
* 内存消耗 38.4 MB
*/
private static boolean verifyBT(TreeNode head, List<Integer> max) {
boolean result = true;
if (head != null) {
result = result & verifyBT(head.getLeft(), max);
int val = head.getValue();
if (max.size() > 0 && max.get(0)>= val) {
return false;
}
max.add(0, Math.max(max.size() > 0 ? max.get(0) : Integer.MIN_VALUE, val));
result = result & verifyBT(head.getRight(), max);
}
return result;
}
/**
* 改用数组存储
* 执行用时: 0 ms
* 内存消耗: 38 MB
*/
private static boolean verifyBTV2(TreeNode head, long[] max) {
boolean result = true;
if (head != null) {
result = result & verifyBTV2(head.getLeft(), max);
int val = head.getValue();
if (max[0]>= val) {
return false;
}
max[0] = Math.max(max[0], val);
result = result & verifyBTV2(head.getRight(), max);
}
return result;
}
/**
* 每一个子树, 往左走, 最大的是根, 往右走最小的是根
* 执行用时: 0 ms
* 内存消耗: 37.9 MB
*/
private static boolean verifyBTV3(TreeNode head, long min, long max) {
if (head == null) {
return true;
}
long val = head.getValue();
if (val <= min || val >= max) {
return false;
}
return verifyBTV3(head.getLeft(), min, val) && verifyBTV3(head.getRight(), val, max);
}
拓展下二叉树相关的基本操作
- 创建二叉树， 一颗二叉树需要两种遍历才可以唯一的确定
下面使用了先序遍历和中序遍历创建二叉树
补充完整的完全二叉树层次遍历数组创建二叉树- 二叉树的遍历， 先序中序后序， 递归和迭代分别编写，层次遍历
二叉树的层次遍历和图的广度遍历相似，只不过图的广度遍历需要增加去重（可能有环）
/**
* @Author: vividzcs
* @Date: 2021/1/30 4:05 下午
*/
public class NodeTree {
private int value;
private NodeTree left;
private NodeTree right;
public NodeTree(int value) {
this.value = value;
}
public static void main(String[] args) {
int[] pre = {1,3,5,7,8,6,4};
int[] mid = {3,7,5,8,1,4,6};
Map<Integer, Integer> indexes = new HashMap<>();
for (int i=0; i<mid.length; i++) {
indexes.put(mid[i], i);
}
NodeTree head = NodeTree.createTree(indexes, pre, mid, 0, pre.length - 1, 0, mid.length - 1);
int[] arr = {3,9,20,-1,-1,15,7};
NodeTree head1 = NodeTree.createTree(arr);
head1.lastOrder(head1);
System.out.println();
head1.iteratorLastOrder(head1);
}
public NodeTree mirro(NodeTree head) {
if (head == null) {
return null;
}
NodeTree tmp = head.left;
head.setLeft(head.getRight());
head.setRight(tmp);
mirro(head.getLeft());
mirro(head.getRight());
return head;
}
/**
* 先序遍历+中序遍历创建二叉树
*/
public static NodeTree createTree(Map<Integer, Integer> indexes, int[] pre, int[] mid, int pStart, int pEnd, int mStart, int mEnd) {
if (pStart > pEnd || mStart > mEnd) {
return null;
}
NodeTree head = new NodeTree(pre[pStart]);
int indexInMid = indexes.get(pre[pStart]);
head.setLeft(createTree(indexes, pre, mid, pStart + 1, indexInMid - mStart + pStart, mStart, indexInMid - 1));
head.setRight(createTree(indexes, pre, mid, indexInMid - mStart + pStart+1, pEnd, indexInMid + 1, mEnd));
return head;
}
/**
* 根据完全二叉树的数组创建二叉树
*/
public static NodeTree createTree(int[] arr) {
if (arr.length < 1) {
return null;
}
NodeTree head = new NodeTree(arr[0]);
List<NodeTree> queue = new ArrayList<>();
queue.add(head);
int index = 0;
while (queue.size() > 0 && index < arr.length) {
NodeTree currentNode = queue.remove(0);
index++;
if (index < arr.length && arr[index] != -1) {
currentNode.setLeft(new NodeTree(arr[index]));
queue.add(currentNode.getLeft());
}
index++;
if (index < arr.length && arr[index] != -1) {
currentNode.setRight(new NodeTree(arr[index]));
queue.add(currentNode.getRight());
}
}
return head;
}
/**
* 迭代 先序遍历
* @param head
*/
public void preOrderIterator(NodeTree head) {
if (head == null) {
return;
}
List<NodeTree> stack = new ArrayList<>();
NodeTree currentNode = head;
while (currentNode != null || stack.size() > 0) {
if (currentNode == null) {
currentNode = stack.remove(stack.size() - 1);
}
if (currentNode.right != null) {
stack.add(currentNode.right);
}
System.out.print(currentNode.value + " ");
currentNode = currentNode.left;
}
}
/**
* 递归先序遍历
* @param head
*/
public void preOrder(NodeTree head) {
if (head != null) {
System.out.print(head.value + " ");
preOrder(head.left);
preOrder(head.right);
}
}
/**
* 迭代中序遍历
* @param head
*/
public void iteratorMinOrder(NodeTree head) {
if (head == null) {
return;
}
List<NodeTree> stack = new ArrayList<>();
Set<NodeTree> set = new HashSet<>();
stack.add(head);
while (stack.size() > 0) {
NodeTree currentNode = stack.get(stack.size() - 1);
while (currentNode.getLeft() != null && !set.contains(currentNode.getLeft())) {
stack.add(currentNode.getLeft());
currentNode = currentNode.getLeft();
}
currentNode = stack.remove(stack.size() - 1);
set.add(currentNode);
System.out.print(currentNode.getValue() + " ");
if (currentNode.getRight() != null) {
stack.add(currentNode.getRight());
}
}
}
/**
* 中序遍历
* @param head
*/
public void minOrder(NodeTree head) {
if (head != null) {
minOrder(head.left);
System.out.print(head.value + " ");
minOrder(head.right);
}
}
public void iteratorLastOrder(NodeTree head) {
if (head == null) {
return;
}
List<NodeTree> stack = new ArrayList<>();
Set<NodeTree> set = new HashSet<>();
stack.add(head);
while (stack.size() > 0) {
NodeTree currentNode = stack.get(stack.size() - 1);
while (currentNode.getLeft() != null && !set.contains(currentNode.getLeft())) {
stack.add(currentNode.getLeft());
currentNode = currentNode.getLeft();
}
if (currentNode.getRight() != null && !set.contains(currentNode.getRight())) {
stack.add(currentNode.getRight());
} else {
NodeTree temp = stack.remove(stack.size() - 1);
System.out.print(temp.value + " ");
set.add(temp);
}
}
}
/**
* 后序遍历
* @param head
*/
public void lastOrder(NodeTree head) {
if (head != null) {
lastOrder(head.getLeft());
lastOrder(head.getRight());
System.out.print(head.value + " ");
}
}
/**
* 层次遍历
* @param head
*/
public void levelIterator(NodeTree head) {
List<NodeTree> queue = new ArrayList<>();
queue.add(head);
while (queue.size() > 0) {
NodeTree currentNode = queue.remove(0);
System.out.print(currentNode.value + " ");
if (currentNode.getLeft() != null) {
queue.add(currentNode.getLeft());
}
if (currentNode.getRight() != null) {
queue.add(currentNode.getRight());
}
}
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public NodeTree getLeft() {
return left;
}
public void setLeft(NodeTree left) {
this.left = left;
}
public NodeTree getRight() {
return right;
}
public void setRight(NodeTree right) {
this.right = right;
}
}
