题目：
给定一棵非空二叉树，数据域值为不等于0的整数。请编写程序找出其最深层间隔最远的两个结点，输出这两个结点差的绝对值。如图1所示的各二叉树最深层间隔最远的结点为5和8。如果最深层只有一个结点，则输出0。
输入格式:
输入为一组用空格间隔的整数，个数不超过200个，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。
输出格式:
输出为一个整数，为二叉树最深层间隔最远的两个结点差的绝对值，如果最深层只有一个结点，则输出0。
输入样例1:
1 2 0 5 0 0 3 6 0 0 8 0 0输出样例1:
在这里给出相应的输出。例如：
3?思路
采用中序遍历法时，遍历规则是 左 -中 -右，最深层第一个被遍历到的节点一定是最深层最左边的节点，最深层最后一个被遍历的节点一定是最后一个节点。
在创建二叉树时需要给每个节点添加一个depth深度属性，方便遍历查找。
节点类
class MyNode{
String val;
MyNode left;
MyNode right;
int depth;
public MyNode(){
}
}创建二叉树
public MyNode createTree(){
MyNode node;
String ch=array[index];//这是输入的数据
index++;//下标++
if (ch.equals("0")){
node=null;
}else{
depth++;//深度++
node=new MyNode();
node.depth=depth;
node.val=ch;
node.left=createTree();//创建子树
depth=node.depth;//修正层数
node.right=createTree();
if (node.depth>maxDepth)
maxDepth=node.depth;
}
return node;
}Tree类
class Tree{
MyNode root;
int index;
String[] array;
int depth;//记录最大深度
int maxDepth;
MyNode[] distance;//第一个记录深度最左边的节点，第二个记录最右边的节点
public Tree(String[] array){
this.array=array;
maxDepth=0;
depth=0;
distance=new MyNode[2];
root=createTree();
}
public MyNode createTree(){
MyNode node;
String ch=array[index];
index++;//下标++
if (ch.equals("0")){
node=null;
}else{
depth++;//深度++
node=new MyNode();
node.depth=depth;
node.val=ch;
node.left=createTree();//创建子树
depth=node.depth;//修正层数
node.right=createTree();
if (node.depth>maxDepth)
maxDepth=node.depth;
}
return node;
}
public int compute(){
search(root);
if (distance[0]!=null&&distance[1]!=null)
return Math.abs(Integer.parseInt(distance[0].val)-Integer.parseInt(distance[1].val));
else
return 0;//只有一个节点返回0
}
public void search(MyNode node){
if (node==null)
return;
if (node.left!=null)
search(node.left);
if (node.depth==maxDepth){//等于最大深度
if (distance[0]!=null)//最左节点不为空
distance[1]=node;//覆盖最右节点
else
distance[0]=node;
}
if (node.right!=null)
search(node.right);
}
}完整代码
import java.util.Scanner;
public class test5 {
static Scanner input=new Scanner(System.in);
public static void main(String[] args) {
String[] array=input.nextLine().split(" ");
Tree tree=new Tree(array);
System.out.println(tree.compute());
}
}
class Tree{
MyNode root;
int index;
String[] array;
int depth;//记录最大深度
int maxDepth;
MyNode[] distance;//第一个记录深度最左边的节点，第二个记录最右边的节点
public Tree(String[] array){
this.array=array;
maxDepth=0;
depth=0;
distance=new MyNode[2];
root=createTree();
}
public MyNode createTree(){
MyNode node;
String ch=array[index];
index++;//下标++
if (ch.equals("0")){
node=null;
}else{
depth++;//深度++
node=new MyNode();
node.depth=depth;
node.val=ch;
node.left=createTree();//创建子树
depth=node.depth;//修正层数
node.right=createTree();
if (node.depth>maxDepth)
maxDepth=node.depth;
}
return node;
}
public int compute(){
search(root);
if (distance[0]!=null&&distance[1]!=null)
return Math.abs(Integer.parseInt(distance[0].val)-Integer.parseInt(distance[1].val));
else
return 0;//只有一个节点返回0
}
public void search(MyNode node){
if (node==null)
return;
if (node.left!=null)
search(node.left);
if (node.depth==maxDepth){
if (distance[0]!=null)
distance[1]=node;
else
distance[0]=node;
}
if (node.right!=null)
search(node.right);
}
}
class MyNode{
String val;
MyNode left;
MyNode right;
int depth;
public MyNode(){
}
}