ツリーの第K層のノードの個数を求めます

タイトル:ツリーの第k層のノードの個数を求めます:
考え方:
1.再帰:ルートがrootである二叉木の第k層ノードの個数を求めるのは、rootを要求することである.left第k-1層ノードの個数+root.right第k-1層ノードの個数

public static int getNumberOfKLevel(TreeNode root,int k){
        if(root == null || k <1)
            return 0;
        if(k == 1)
            return 1;
        int numLeft = getNumberOfKLevel(root.left,k-1);
        int numRight = getNumberOfKLevel(root.right,k-1);
        return numLeft+numRight;
    }

2.反復:キューを利用することは,二叉木の高さを求めることに相当し,どの層の高さを求めるかにすぎない.

public static int getNumberOfLevelK(TreeNode root,int k){
        if(root == null || k <1)
            return 0;
        if(k == 1)
            return 1;
        Queue queue = new LinkedList();
        int num = 1;
        int currentLevelNum = 0;
        
        queue.add(root);
        while(k >1){
            while(num > 0){
                TreeNode node = queue.remove();
                if(node.left != null){
                    queue.add(node.left);
                    currentLevelNum++;
                }
                if(node.right != null){
                    queue.add(node.right);
                    currentLevelNum++;
                }
                num --;
            }
            num = currentLevelNum;
            k--;
        }
        
        return queue.size();
    }

 
転載先:https://www.cnblogs.com/lfdingye/p/7364093.html