二叉树的节点个数、叶子节点个数、第k层的节点个数

快来打我* 2022-05-10 23:40 161阅读 0赞

[https://blog.csdn.net/universe\_ant/article/details/72993214][https_blog.csdn.net_universe_ant_article_details_72993214]

class BinaryTreeNode {
         
     	int val;
     	BinaryTreeNode left = null;
     	BinaryTreeNode right = null;
     }
      
     public class NodesStatistics {
         
     	/**
     	 * 求二叉树的节点个数
     	 * (1)如果二叉树为空，节点个数为0；
     	 * (2)如果二叉树不为空，二叉树节点个数 = 左子节点个数 + 右子节点个数 + 1。
     	 * @param root 根节点
     	 * @return 节点个数
     	 */
     	public int getNodesNum(BinaryTreeNode root) {
         
     		if(root == null)
     			return 0;
     		return getNodesNum(root.left) + getNodesNum(root.right) + 1;
     	}
     	
     	/**
     	 * 求二叉树中叶子节点的个数
     	 * (1)如果二叉树为空，返回0；
     	 * (2)如果二叉树不为空，返回1；
     	 * (3)如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。
     	 * @param root 根节点
     	 * @return 叶子节点个数
     	 */
     	public int getLeafNum(BinaryTreeNode root) {
         
     		if(root == null)
     			return 0;
     		if(root.left == null && root.right == null)
     			return 1;
     		int leftNums = getLeafNum(root.left);
     		int rightNums = getLeafNum(root.right);
     		return leftNums + rightNums;
     	}
     	
     	/**
     	 * 求二叉树第k层的节点个数，假设根节点为第0层
     	 * @param root 根节点
     	 * @param k 第k层
     	 * @return 第k层的节点个数
     	 */
     	public int getNodeNumsOnKthLevel(BinaryTreeNode root, int k) {
         
     		if(root == null || k < 0)
     			return 0;
     		if(k == 0)
     			return 1;
     		int leftNodeNums = getNodeNumsOnKthLevel(root.left, k-1);
     		int rightNodeNums = getNodeNumsOnKthLevel(root.right, k-1);
     		return leftNodeNums + rightNodeNums;
     	}
     }
     ```

[https_blog.csdn.net_universe_ant_article_details_72993214]: https://blog.csdn.net/universe_ant/article/details/72993214