步骤一:判断是否为搜索二叉树
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
1.递归方法:
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long lower, long upper) {
if (root == null) {
return true;
}
if (root.val <= lower || root.val >= upper) {
return false;
}
return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
}
2.判断中序遍历的结果是否是升序public boolean isValidBST(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>(10);
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop();
list.add(curr.val);
curr = curr.right;
}
}
for (int i = 1; i < list.size(); i++) {
if (list.get(i) <= list.get(i-1)) {
return false;
}
}
return true;
}
步骤二:判断是否为完全二叉树
一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (queue.peek() != null) {
TreeNode node = queue.poll();
queue.offer(node.left);
queue.offer(node.right);
}
while (!queue.isEmpty() && queue.peek() == null) {
queue.poll();
}
return queue.isEmpty();
}
最后:
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
long pre = Long.MIN_VALUE;
public boolean[] judgeIt (TreeNode root) {
// write code here
return new boolean[]{isSBT(root, Long.MIN_VALUE, Long.MAX_VALUE),isCBT(root)};
}
/**
* 判断一棵二叉树是否为搜索二叉树,只要改写一个二叉树中序遍历,在遍历的过程中看节点值是否都是递增的即可。
* @param root
* @return
*/
public boolean isSBT(TreeNode root, long lower, long upper) {
if (root == null) return true;
if (root.val <= lower || root.val >= upper) return false;
return isSBT(root.left, lower, root.val) && isSBT(root.right, root.val, upper);
}
/**
1.层次遍历直至遇到第一个空节点
2.完全二叉树在遇到空节点之后剩余的应当全是空节点
*/
public boolean isCBT(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (queue.peek() != null) {
TreeNode node = queue.poll();
queue.offer(node.left);
queue.offer(node.right);
}
while (!queue.isEmpty() && queue.peek() == null) {
queue.poll();
}
return queue.isEmpty();
}
}

京公网安备 11010502036488号