用java验证二叉树性质 ： n0 = n2 + 1
创新互联专业为企业提供巢湖网站建设、巢湖做网站、巢湖网站设计、巢湖网站制作等企业网站建设、网页设计与制作、巢湖企业网站模板建站服务，十余年巢湖做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
代码如下
package org.link.tree;
/**
* 树节点
* @author link
*
*/
class TreeNode
{
int data;
TreeNode lchild ; // 左子节点
TreeNode rchild ; // 右子节点
public int getData()
{
return data;
}
public TreeNode getLchild()
{
return lchild;
}
public TreeNode getRchild()
{
return rchild;
}
public void setNode(int data,TreeNode lc,TreeNode rc){
this.data = data;
lchild = lc;
rchild = rc;
}
public TreeNode(){
}
}
class Counter{
public static int count=0;
}
public class TreeTest
{
static int n0; // 0度节点
static int n2; // 2度节点
/**
* 根据传入参数创建二叉树
* @param root
* @param a
* @param i
* @return
*/
public static TreeNode createTree(TreeNode root, int[]a, int i)
{
if(i a.length)
{
if(a[i] == 0)
{
root = null;
}
else
{
TreeNode tl = new TreeNode();
TreeNode tr = new TreeNode();
root.setNode(a[i],createTree(tl,a,++(Counter.count)),createTree(tr,a,++(Counter.count)));
}
}
return root;
}
/**
* 遍历二叉树，记录n0 和 n2
* @param root
*/
public static void traverse(TreeNode root)
{
int degree = 0;
if(root != null)
{
if(root.getLchild() != null)
degree++;
if(root.getRchild() != null)
degree++;
if(degree == 0){
n0++;
}else if(degree == 2){
n2++;
}
traverse(root.getLchild());
traverse(root.getRchild());
}else{
}
}
public static void main(String[] args)
{
int[] a = {1,2,3,0,0,4,0,0,5,0,0}; // 这是你传入的任意二叉树数组
TreeNode root = new TreeNode();
root = createTree(root,a,Counter.count);
traverse(root);
System.out.println("n0:" + n0 + ",n2:" + n2);
// 验证n0=n2+1
if(n0 == n2 + 1){
System.out.println("n0=n2+1");
}else{
System.out.println("输入节点数组有误");
}
}
}
java 判断两个二叉树是否完全相同
包括了创建二叉树，前序遍历输出（递归），比较二叉树是否相同。
[java] view plain copy
package com.yuxin.learn;
import java.util.LinkedList;
public class Main {
private static int[] a1 = { 1, 2, 3, 4, 5, 6 };
private static int[] a2 = { 1, 2, 5, 6, 7 };
private static int[] a3 = { 1, 2, 5, 6, 7 };
private static int[] a4 = { 1, 2, 5, 6, 7, 5, 6 };
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public static TreeNode createTree(int a[]) {
int len = a.length;
// 将数组的值依次转为Node节点
LinkedListTreeNode list = new LinkedListTreeNode();
for (int i = 0; i len; i++){
list.add(new TreeNode(a[i]));
}
for (int i = 0; i len / 2 - 1; i++) {
list.get(i).left = list.get(i * 2 + 1);
list.get(i).right = list.get(i * 2 + 2);
}
// 最后一个父节点可能没有右边孩子
int last = len / 2 - 1;
list.get(last).left = list.get(last * 2 + 1);
if (len % 2 == 1) {
list.get(last).right = list.get(last * 2 + 2);
}
return list.get(0);
}
//递归前序遍历输出二叉树
public static void preOder(TreeNode head){
System.out.print(head.val+" ");
if(head.left!=null) preOder(head.left);
if(head.right!=null) preOder(head.right);
}
//递归判断两个二叉树是否相同
public static boolean isSameTree(TreeNode head1, TreeNode head2) {
if ((head1 == null head2 != null) || (head1 != null)
(head2 == null) || (head1.val != head2.val))
return false;
if (head1.left == null head1.right == null head2.left == null
head2.right == null head1.val == head2.val)
return true;
return isSameTree(head1.left, head2.left)
isSameTree(head1.right, head2.right);
}
public static void main(String[] args) {
TreeNode head1 = createTree(a1);
System.out.println("Tree1:");
preOder(head1);
System.out.println();
TreeNode head2 = createTree(a2);
System.out.println("Tree2:");
preOder(head2);
System.out.println();
TreeNode head3 = createTree(a3);
System.out.println("Tree3:");
preOder(head3);
System.out.println();
TreeNode head4 = createTree(a4);
System.out.println("Tree4:");
preOder(head4);
System.out.println();
System.out.println("Tree1和Tree2相同吗？" + isSameTree(head1, head2));
System.out.println("Tree2和Tree3相同吗？" + isSameTree(head2, head3));
System.out.println("Tree3和Tree4相同吗？" + isSameTree(head3, head4));
}
}
java判断一个二叉树是不是合法的二分查找树
/* 判断一个二叉树是不是合法的二分查找树的简单的递给方法，学习
* 采用自顶向下的遍历方式，对于每个节点，检查顶部传来的范围要求，
* 要求是指：对于左子树，父节点的值就是最大值，对于右子树，父节点的值就是最小值
*/
public boolean isValidBST(TreeNode root) {
//初始的时候，对根节点没有范围要求
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
//检查是否满足根节点的范围要求
if (root.val = maxVal || root.val = minVal)
return false;
//修改对子节点的要求，对于左子树，本节点的值就是最大值，对于右子树，本节点的值就是最小值
return isValidBST(root.left, minVal, root.val) isValidBST(root.right, root.val, maxVal);
