首页 / 算法 / LeetCode 222. 完全二叉树的节点个数（Count Complete Tree Nodes）

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 222. 完全二叉树的节点个数（Count Complete Tree Nodes），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1000字，纯文字阅读大概需要2分钟。

内容图文

题目描述

 

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例: 

            输入: 
    1
   /   2   3
 / \  /
4  5 6

输出: 6

 

解题思路

 

 从根节点开始分别判断左右子树的高度：

  • 若左子树高度等于右子树，说明左子树一定为满二叉树，可得左子树的总节点个数，然后递归求右子树的节点数；
  • 若左子树高度大于右子树，说明右子树一定为满二叉树，可得右子树的总节点个数，然后递归求左子树的节点数。

 

代码

 

             1
            /*
            *

             2
             * Definition for a binary tree node.

             3
             * struct TreeNode {

             4
             *     int val;

             5
             *     TreeNode *left;

             6
             *     TreeNode *right;

             7
             *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

             8
             * };

             9
            */
            10
            class
             Solution {

            11
            public
            :

            12
            int countNodes(TreeNode* root) {
13if(root == NULL) return0;
14int left = height(root->left), right = height(root->right);
15if(left == right)
16return (1 << left) + countNodes(root->right);
17else18return countNodes(root->left) + (1 << right);
19    }
20int height(TreeNode* root){
21if(root == NULL)
22return0;
23return height(root->left) + 1;
24    }
25 };

 

原文：https://www.cnblogs.com/wmx24/p/10273403.html

内容总结

以上是互联网集市为您收集整理的LeetCode 222. 完全二叉树的节点个数（Count Complete Tree Nodes）全部内容，希望文章能够帮你解决LeetCode 222. 完全二叉树的节点个数（Count Complete Tree Nodes）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1253327.html

来源：【匿名】