一、二叉树最大深度(高度)
//二叉树的最大深度/高度(DFS )公共嵌入最大深度1 )节点根(if )根==空)//空树的高度为0返回0； } intleftdepth=max depth1(root.left )； //递归计算左部分树的高度intrightdepth=max depth1(根. right )//递归计算右部分树的高度returnmath.max(leftdepth，rightDepth ) 1 //提取左右子树的最大值，求出根节点的高度为1}//二叉树的最大深度/高度(BFS ) public int max depth2(node root ) ) if(root==null ) /空}队列节点队列=new linked list (； queue.offer (根)； //将根节点排队的int res=0； //保存二叉树的高度while (！ queue.isEmpty ()//遍历每一层的int size=queue.size )； //当前层的节点数while(size0) {Node temp=queue.poll )； if(temp.left！=null(//排队到当前节点的左节点的queue.offer(temp.left )； (if ) temp.right！=null(//排队到当前节点的右节点的queue.offer(temp.right )； (尺寸---； (RES； 每遍历//1层，递增1个层数(}return res； } 二、二叉树结点个数
//求二叉树的节点数(方法1 )公共内节点计数1 )节点根) if (根==空) ) {返回0； }返回节点计数1 (根. left )节点计数1 (根. right ) 1； //求二叉树节点数(方法2 )公共静态int count2=0； //节点数publicintnodecount2(noderoot ) {//int res=0； //记录节点数if (root==null ) {return 0； }count2； //在遍历过程中，所有节点都访问并在每次访问一个节点时向计数2添加节点计数2 (根. left )。 节点计数2 (根. right )； 返回计数2； //求二叉树的节点数(方法3 )公共int node count3) noderoot ) {int res=0； //记录节点的个数if(root==null ) ) /空树直接返回0return 0； }堆叠堆栈=new堆栈(； stack.push (根)； while (！ stack.isEmpty () {Node temp=stack.pop； res； //在遍历过程中所有节点都可以访问，每次访问一个节点时都会向res添加if(temp.left )！=null}{stack.push(temp.left )； (if ) temp.right！=null(stack.push(temp.right )； } }返回RES； } 三、二叉树叶子结点个数
//求二叉树叶数(方法1 ) publicintleafcount1) node root (if (root==null ) ) /空树直接返回0return 0； } if (root.left==null root.right==null ) (/没有左右子树的是叶的节点return 1； }returnleafcount1(root.left ) leaf count1(root.right )； //求二叉树叶数(方法2 )公共静态int count1=0； 记录//叶的节点数(该count1定义必须置于函数之外。 否则，在每次遍历时重新执行整个函数时=并将count1重置为零。 下面的count2也一样) publicintleafcount2(节点根) {//int res=0； //记录叶节点的个数if (root==null ) )//空树直接返回0返回0； } if (root.left==null root.right==null ) /无左右子树是叶节点在count1上加上count1； (else )//否则继续遍历，左右孩子继续查找空节点leafcount2(root.left )。 leaf count2(根. right； }返回计数1； //求二叉树叶数(方法3 ) publicintleafcount3) noderoot ) {int res=0； //记录叶节点的个数if (root==null ) )//空树直接返回0返回0； }堆叠堆栈=new堆栈(； sta
ck.push(root);while(!stack.isEmpty()) {Node temp=stack.pop();if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一res++;}if(temp.left!=null) {stack.push(temp.left);}if(temp.right!=null) {stack.push(temp.right);}}return res;}四、二叉树第k层结点个数
//求第k层结点个数public int kLevelCount(Node root,int k) {if(root==null) {//空树直接返回0return 0;}if(k==1) {//k==1即求根节点的个数，直接返回1return 1;}return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数}五、完整代码实现
package fighting;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class BinaryTree {public Node BuildTree() {//构造二叉树Node A=new Node('A');Node B=new Node('B'); Node C=new Node('C'); Node D=new Node('D'); Node E=new Node('E'); Node F=new Node('F'); Node G=new Node('G'); Node H=new Node('H'); A.left=B; A.right=C; B.left=D; B.right=E; C.left=F; C.right=G; E.right=H; return A;}//求二叉树最大深度/高度(DFS)public int maxDepth1(Node root) {if(root==null) {//空树高度为0return 0;}int leftDepth=maxDepth1(root.left);//递归计算左子树高度int rightDepth=maxDepth1(root.right);//递归计算右子树高度return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1}//求二叉树最大深度/高度(BFS)public int maxDepth2(Node root) {if(root==null) {//空树高度为0return 0;}Queue<Node> queue=new LinkedList<>();queue.offer(root);//将根结点入队列int res=0;//保存二叉树的高度while(!queue.isEmpty()) {//遍历每层int size=queue.size();//当前层的结点数量while(size>0) {Node temp=queue.poll();if(temp.left!=null) {//当前结点左节点存在入队列queue.offer(temp.left);}if(temp.right!=null) {//当前结点右节点存在入队列queue.offer(temp.right);}size--;}res++;//每遍历完一层，将层数加一}return res;}//求二叉树的叶子数(方法一)public int leafCount1(Node root){if(root==null) {//空树直接返回0return 0;}if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点return 1;}return leafCount1(root.left)+leafCount1(root.right);}//求二叉树的叶子数(方法二)public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外，否则每次遍历时重新进行函数体时有=又重新将count1置为零，下面的count2同理)public int leafCount2(Node root) {// int res=0;//记录叶子结点的个数if (root == null) {// 空树直接返回0return 0;}if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一count1++;} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点leafCount2(root.left);leafCount2(root.right);}return count1;}//求二叉树的叶子数(方法三)public int leafCount3(Node root) {int res=0;//记录叶子结点的个数if (root == null) {//空树直接返回0return 0;}Stack<Node> stack=new Stack<>();stack.push(root);while(!stack.isEmpty()) {Node temp=stack.pop();if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一res++;}if(temp.left!=null) {stack.push(temp.left);}if(temp.right!=null) {stack.push(temp.right);}}return res;}//求二叉树的结点数(方法一)public int nodeCount1(Node root) {if(root==null) {return 0;}return nodeCount1(root.left)+nodeCount1(root.right)+1;}//求二叉树的结点数(方法二)public static int count2 = 0;// 记录结点个数public int nodeCount2(Node root) {//int res = 0;// 记录结点个数if (root == null) {return 0;}count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一nodeCount2(root.left);nodeCount2(root.right);return count2;}// 求二叉树的结点数(方法三)public int nodeCount3(Node root) {int res = 0;// 记录结点的个数if (root == null) {// 空树直接返回0return 0;}Stack<Node> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {Node temp = stack.pop();res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一if (temp.left != null) {stack.push(temp.left);}if (temp.right != null) {stack.push(temp.right);}}return res;}//求第k层结点个数public int kLevelCount(Node root,int k) {if(root==null) {//空树直接返回0return 0;}if(k==1) {//k==1即求根节点的个数，直接返回1return 1;}return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数}public static void main(String[] args) {BinaryTree binaryTree=new BinaryTree();Node root=binaryTree.BuildTree();System.out.println("二叉树的最大高度为(DFS):"+binaryTree.maxDepth1(root));//DFS求二叉树高度System.out.println("二叉树的最大高度为(BFS):"+binaryTree.maxDepth2(root));//BFS求二叉树高度System.out.println("二叉树结点的个数为(方法一)："+binaryTree.nodeCount1(root));System.out.println("二叉树结点的个数为(方法二)："+binaryTree.nodeCount2(root));System.out.println("二叉树结点的个数为(方法三)："+binaryTree.nodeCount3(root));System.out.println("二叉树叶子结点的个数为(方法一)："+binaryTree.leafCount1(root));System.out.println("二叉树叶子结点的个数为(方法二)："+binaryTree.leafCount2(root));System.out.println("二叉树叶子结点的个数为(方法三)："+binaryTree.leafCount3(root));System.out.printf("二叉树第%d层结点个数数为：%d",3,binaryTree.kLevelCount(root,3));}}class Node{char val;Node left;Node right;public Node(char val) {//Node的构造函数this.val=val;}}运行结果：
二叉树的最大高度为(DFS):4二叉树的最大高度为(BFS):4二叉树结点的个数为(方法一)：8二叉树结点的个数为(方法二)：8二叉树结点的个数为(方法三)：8二叉树叶子结点的个数为(方法一)：4二叉树叶子结点的个数为(方法二)：4二叉树叶子结点的个数为(方法三)：4二叉树第3层结点个数数为：4该实例的二叉树图如下所示：