首页 > 代码库 > 求二叉树第k层的结点个数
求二叉树第k层的结点个数
tag: 二叉树 - 层次遍历
思路: 用层次遍历思路求解
辅助: 队列
package com.zhaochao.tree; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /** * Created by zhaochao on 17/1/23. */ public class NodesNumberKLevel { public int getNodesNumberKLevel(TreeNode root, int k) { int count = 0; if(root == null || k <= 0 || k > getDepthOfTree(root)) { return count; } if(k == 1) { return 1; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while(!queue.isEmpty()) { int size = queue.size(); if(count == k - 1) { return size; } ArrayList<Integer> level = new ArrayList<Integer>(); for(int i = 0; i < size; i++) { TreeNode head = queue.poll(); level.add(head.val); if(head.left != null) { queue.offer(head.left); } if(head.right != null) { queue.offer(head.right); } } count++; } return count; } public int getDepthOfTree(TreeNode root) { if(root == null) { return 0; } int left = getDepthOfTree(root.left); int right = getDepthOfTree(root.right); return Math.max(left,right) + 1; } public static void main(String[] args) { TreeNode root = new TreeNode(0); TreeNode node1 = new TreeNode(1); TreeNode node2 = new TreeNode(2); TreeNode node3 = new TreeNode(3); root.left = node1; root.right = node2; node2.left = node3; NodesNumberKLevel test = new NodesNumberKLevel(); int numbers = 0; numbers = test.getNodesNumberKLevel(root, 3); System.out.println("The numbers of nodes of level 3 is : " + numbers); } }
求二叉树第k层的结点个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。