題目地址
https://leetcode-cn.com/problems/validate-binary-search-tree
題目描述
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設(shè)一個二叉搜索樹具有如下特征：
節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
根節(jié)點(diǎn)的值為 5 ，但是其右子節(jié)點(diǎn)值為 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);
}
/**
* 二叉搜索樹的中序遍歷是遞增序列
* 運(yùn)行時間 1 ms
* 內(nèi)存消耗 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;
}
/**
* 改用數(shù)組存儲
* 執(zhí)行用時: 0 ms
* 內(nèi)存消耗: 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;
}
/**
* 每一個子樹, 往左走, 最大的是根, 往右走最小的是根
* 執(zhí)行用時: 0 ms
* 內(nèi)存消耗: 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);
}
拓展下二叉樹相關(guān)的基本操作
- 創(chuàng)建二叉樹， 一顆二叉樹需要兩種遍歷才可以唯一的確定
下面使用了先序遍歷和中序遍歷創(chuàng)建二叉樹
補(bǔ)充完整的完全二叉樹層次遍歷數(shù)組創(chuàng)建二叉樹- 二叉樹的遍歷， 先序中序后序， 遞歸和迭代分別編寫，層次遍歷
二叉樹的層次遍歷和圖的廣度遍歷相似，只不過圖的廣度遍歷需要增加去重（可能有環(huán)）
/**
* @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;
}
/**
* 先序遍歷+中序遍歷創(chuàng)建二叉樹
*/
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;
}
/**
* 根據(jù)完全二叉樹的數(shù)組創(chuàng)建二叉樹
*/
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;
}
}
