Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)

222. The number of nodes in a complete binary tree

Force button topic link

Give a completely binary tree , Find out the number of nodes of the tree .

Example 1：

• Input ：root = [1,2,3,4,5,6]
• Output ：6

Example 2：

• Input ：root = []
• Output ：0

Example 3：

• Input ：root = [1]
• Output ：1

Tips ：

• The number of nodes in the tree ranges from [0, 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• The topic data ensures that the input tree is Perfect binary tree

Direct sequence traversal search , It can be regarded as a happy method .

package com.programmercarl.tree;

import java.util.ArrayDeque;
import java.util.Deque;

/** * @ClassName CountNodes * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 10:15 * @Version 1.0 * https://leetcode.cn/problems/count-complete-tree-nodes/ * 222.  The number of nodes in a complete binary tree  **/
public class CountNodes {
    
    public int countNodes(TreeNode root) {
    
        /** *  Sequence traversal  */
        if (root == null) {
    
            return 0;
        }
        Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
        deque.offer(root);
        int sum = 0;
        while (!deque.isEmpty()) {
    
            int size = deque.size();
            while (size > 0) {
    
                root = deque.pop();
                sum++;
                if (root.left != null) {
    
                    deque.offer(root.left);
                }
                if (root.right != null) {
    
                    deque.offer(root.right);
                }
                size--;
            }
        }
        return sum;
    }
}

According to the properties of full binary tree , Number of nodes = front n-1 Number of layer nodes + Number of nodes in the last layer
front n-1 Number of layer nodes = 2^(n-1) -1

    /** *  According to the properties of complete binary tree  * * @param root * @return */
    public int countNodes(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (leftDepth == rightDepth) {
    
            // If the depth is equal , Then the left side is full of binary trees 
            // leftDepth Is to calculate the depth from the head node of the current subtree , Not the root node of two trees 
            // ( 2 ^ leftDepth - 1 ) + 1 1 It is the root node of two trees 
            return ((1 << leftDepth) - 1) + 1 + countNodes(root.right);
        } else {
    
            // The right subtree is a full binary tree 
            return ((1 << rightDepth) - 1) + 1 + countNodes(root.left);
        }
    }

    /** *  From current subtree   Start to calculate the depth  * * @param root * @return */
    public int getDepth(TreeNode root) {
    
        int depth = 0;
        while (root != null) {
    
            root = root.left;
            depth++;
        }
        return depth;
    }