leetcode 222. Count Complete Tree Nodes | 222. 完全二叉树的节点个数（Java）

Myth丶恋晨 2022-10-08 00:46 142阅读 0赞

## 题目 ##

[https://leetcode.com/problems/count-complete-tree-nodes/][https_leetcode.com_problems_count-complete-tree-nodes]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

> 思路参考左程云《程序员代码面试指南》

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]

##### 顺便贴一下草稿 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]

## 代码 ##

class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode() { 
        }
    
        TreeNode(int val) { 
            this.val = val;
        }
    
        TreeNode(int val, TreeNode left, TreeNode right) { 
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    class Solution { 
        public int countNodes(TreeNode root) { 
            if (root == null) return 0;
            int height = 0;
            TreeNode node = root;
            while (node != null) { 
                node = node.left;
                height++;
            }
            return bs(root, 1, height);
        }
    
        /** * 计算以node为根的树的节点数量 = 左子树节点数量 + 右子树节点数量 + node节点本身 * * @param d current depth * @param h height */
        public int bs(TreeNode node, int d, int h) { 
            if (node == null) return 0;
            int rDepth = d; // 右子树的最左节点的深度
            TreeNode rNode = node.right;
            while (rNode != null) { 
                rDepth++;
                rNode = rNode.left;
            }
            if (rDepth == h) // 情况1：node左子树为满二叉树（可用公式计算节点个数），右子树继续递归计算
                return (1 << (h - d) - 1) + bs(node.right, d + 1, h) + 1;
            else  // 情况2：node右子树为满二叉树（可用公式计算节点个数），左子树继续递归
                return (1 << (h - d - 1)) - 1 + bs(node.left, d + 1, h) + 1;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 7]

[https_leetcode.com_problems_count-complete-tree-nodes]: https://leetcode.com/problems/count-complete-tree-nodes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/3d05f352098f4703aa58332d3f48bde7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/a89b76667450427c85042b1385ecebe5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/838f80569e11433a867be6f9455416b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221005/dbecebf855a042da805c55ebcccb10e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]: /images/20221005/2063413e4f5249478866967576f18314.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]: /images/20221005/53b2a19a758e4775b3f58abba83c3dfd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]: /images/20221005/f2f8066cdc8e40e6babc7b20235069ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 7]: /images/20221005/76405d6b8ccf437eb4d32916baad71bd.png