51做网站,想学app开发哪里有培训班,商业空间设计主要有以下几点,我需要把网站做完全二叉树 的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层#xff0c;则该层包含 1~ 2h 个节点。 因此#xff0c;…完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。 因此完全二叉树只有叶子节点一层的右侧缺少节点对树的左节点和右节点进行递归如果两者深度相同则这棵树的节点数为2^k - 1否则对左右子树进行判断这样即可不用遍历整个树中符合完全二叉树的子树部分就。
注这里的指数运算使用了位运算符而不是 ^一开始使用 ^ 运算符返回的结果与预想的一直不对这个运算符是对两个数按位进行异或而不是幂运算。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {if(root nullptr){return 0;}TreeNode * left root-left;TreeNode * right root-right;int l_depth 0;int r_depth 0;while(left ! nullptr){l_depth;left left-left; }while(right ! nullptr){r_depth;right right-right;}if(l_depth r_depth){return (2 l_depth) - 1;}return countNodes(root-left) countNodes(root-right) 1;}
};
