步骤一:判断是否为搜索二叉树
二叉查找树(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(); } }