## 剑指Offer（Java版）：二叉树的深度 原

一贱书生

package cglib;

class BinaryTreeNode{
int data;

BinaryTreeNode leftNode;
BinaryTreeNode rightNode;

}

public class jiekou {

//普通二叉树求深度
public int treeDepth(BinaryTreeNode root){
if(root == null)
return 0;
System.out.println("treeDepth递归");
int nLeft = treeDepth(root.leftNode);

System.out.println("nLeft="+nLeft);
System.out.println("nRight前treeDepth递归");
int nRight = treeDepth(root.rightNode);
System.out.println("nRight后");
System.out.println("nRight="+nRight);
return (nLeft > nRight)?(nLeft+1):(nRight+1);
}
public static void main(String[] args){
BinaryTreeNode root=new BinaryTreeNode();
BinaryTreeNode node1=new BinaryTreeNode();
BinaryTreeNode node2=new BinaryTreeNode();
BinaryTreeNode node3=new BinaryTreeNode();
BinaryTreeNode node4=new BinaryTreeNode();
BinaryTreeNode node5=new BinaryTreeNode();
BinaryTreeNode node6=new BinaryTreeNode();
root.leftNode=node1;
root.rightNode=node2;
node1.leftNode=node3;
node1.rightNode=node4;
node2.rightNode=node5;
node4.leftNode=node6;
root.data=1;
node1.data=2;
node2.data=3;
node3.data=4;
node4.data=5;
node5.data=6;
node6.data=7;
jiekou test = new jiekou();
System.out.println(test.treeDepth(root));
}
}

package cglib;

class BinaryTreeNode{
int data;

BinaryTreeNode leftNode;
BinaryTreeNode rightNode;

}

public class jiekou {

//普通二叉树求深度
public int treeDepth(BinaryTreeNode root){
if(root == null)
return 0;
System.out.println("treeDepth递归");
int nLeft = treeDepth(root.leftNode);

System.out.println("nLeft="+nLeft);
System.out.println("nRight前treeDepth递归");
int nRight = treeDepth(root.rightNode);
System.out.println("nRight后");
System.out.println("nRight="+nRight);
return (nLeft > nRight)?(nLeft+1):(nRight+1);
}

public boolean isBalanced(BinaryTreeNode root){
if(root ==null)
return true;
int left = treeDepth(root.leftNode);
int right = treeDepth(root.rightNode);
int diff = left - right;
if(diff > 1 || diff <-1)
return false;
return isBalanced(root.leftNode) && isBalanced(root.rightNode);
}
public static void main(String[] args){
BinaryTreeNode root=new BinaryTreeNode();
BinaryTreeNode node1=new BinaryTreeNode();
BinaryTreeNode node2=new BinaryTreeNode();
BinaryTreeNode node3=new BinaryTreeNode();
BinaryTreeNode node4=new BinaryTreeNode();
BinaryTreeNode node5=new BinaryTreeNode();
BinaryTreeNode node6=new BinaryTreeNode();
root.leftNode=node1;
root.rightNode=node2;
node1.leftNode=node3;
node1.rightNode=node4;
node2.rightNode=node5;
node4.leftNode=node6;
root.data=1;
node1.data=2;
node2.data=3;
node3.data=4;
node4.data=5;
node5.data=6;
node6.data=7;
jiekou test = new jiekou();
System.out.println(test.treeDepth(root));
System.out.println(test.isBalanced(root));
}
}

treeDepth递归
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=2
nLeft=3
nRight前treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=1
nRight后
nRight=2
4
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=2
treeDepth递归
nLeft=0
nRight前treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=1
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
nRight后
nRight=0
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
true

package cglib;

class BinaryTreeNode{
int data;

BinaryTreeNode leftNode;
BinaryTreeNode rightNode;

}

public class jiekou {

//普通二叉树求深度
public int treeDepth(BinaryTreeNode root){
if(root == null)
return 0;
System.out.println("treeDepth递归");
int nLeft = treeDepth(root.leftNode);

System.out.println("nLeft="+nLeft);
System.out.println("nRight前treeDepth递归");
int nRight = treeDepth(root.rightNode);
System.out.println("nRight后");
System.out.println("nRight="+nRight);
return (nLeft > nRight)?(nLeft+1):(nRight+1);
}

public boolean isBalanced(BinaryTreeNode root){
if(root ==null)
return true;
int left = treeDepth(root.leftNode);
int right = treeDepth(root.rightNode);
int diff = left - right;
if(diff > 1 || diff <-1)
return false;
return isBalanced(root.leftNode) && isBalanced(root.rightNode);
}

//高效率的判断是否是一棵平衡二叉树
public boolean isBalanced2(BinaryTreeNode root){
int depth = 0;
return isBalanced2(root,depth);
}
public boolean isBalanced2(BinaryTreeNode root,int depth){
if(root == null){
depth = 0;
return true;
}
int left = 0,right = 0;
if(isBalanced2(root.leftNode,left) && isBalanced2(root.rightNode,right)){
int diff = left-right;
if(diff <= 1 && diff >= -1){
depth = 1+(left > right?left : right);
return true;
}
}
return false;
}
public static void main(String[] args){
BinaryTreeNode root=new BinaryTreeNode();
BinaryTreeNode node1=new BinaryTreeNode();
BinaryTreeNode node2=new BinaryTreeNode();
BinaryTreeNode node3=new BinaryTreeNode();
BinaryTreeNode node4=new BinaryTreeNode();
BinaryTreeNode node5=new BinaryTreeNode();
BinaryTreeNode node6=new BinaryTreeNode();
root.leftNode=node1;
root.rightNode=node2;
node1.leftNode=node3;
node1.rightNode=node4;
node2.rightNode=node5;
node4.leftNode=node6;
root.data=1;
node1.data=2;
node2.data=3;
node3.data=4;
node4.data=5;
node5.data=6;
node6.data=7;
jiekou test = new jiekou();
System.out.println(test.treeDepth(root));
System.out.println(test.isBalanced(root));
System.out.println(test.isBalanced2(root));
}
}

### 一贱书生

2018/07/11
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

2018/09/04
0
0
【求助】想进大公司，但是算法不怎么好，该如何规划自己以后的学习？

2015/07/08
1K
14

nanchen2251
2018/07/03
0
0

nanchen2251
2018/07/03
0
0

nproc systemd on CentOS 7

Increasing nproc for processes launched by systemd on CentOS 7 Ask Question I have successfully increased the nofile and nproc value for the local users, but I couldn't find a p......

MtrS

3
0

oixxan__

2
0
springmvc java对象转json，上传下载（未完）拦截器Interceptor以及源码解析（未完待续）

package com.atguigu.my.controller;import java.util.Collection;import org.springframework.beans.factory.annotation.Autowired;import org.springframework.stereotype.Contr......

architect刘源源

29
0
[日更-2019.5.24、25、26] Android系统中的Binder通信机制分析（一）--servicemanager

Captain_小馬佩德罗

24
0

go4it

3
0