222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2 h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
方法一:递归(后序)
思路和后序遍历二叉树差不多,只不过每次返回的是该树的节点总数.
递归三要素:
确定参数和返回值:参数就是传入树的根节点,返回值就是以该节点为根节点二叉树的节点数量
确定结束条件:如果节点为空,就返回0,表示节点数为0.
确定单层递归的逻辑:先求左子树的节点数量,再求右子树的节点数量,最后取和再加一(加1是因为要算上当前所在树的根节点),就是以目前节点为根节点的节点数量.
参考代码1
//递归(后序) 时间O(n) 空间:logn int countNodes(TreeNode* root) { if(root==NULL) { return 0; } int len1 = countNodes(root->left);//左子树节点的个数 int len2 = countNodes(root->right);//右子树节点的个数 return len1+len2+1;//返回到root处节点的总个数 }
方法二:递归(先序)
递归三要素:
- 确定参数和返回值:参数就是传入树的根节点. 由于记录节点个数的遍历时全局变量,所以不需要返回值.
- 确定结束条件:如果节点为叶子节点,就结束.
- 确定单层递归逻辑:先判断做子树是否不为NULL,如果是则cnt++,继续进行递归;左子树判断完毕之后判断右子树…
参考代码2
// 递归(先序) 参数传递为啥不可以用引用呢???---有空试一下 int cnt=0; void calNode(TreeNode* node) { if(node->left==NULL&&node->right==NULL) { return; } if(node->left) { cnt++; calNode(node->left); } if(node->right) { cnt++; calNode(node->right); } } int countNodes(TreeNode* root) { if(root==NULL) { return 0; } cnt++; calNode(root); return cnt; }
方法三:迭代(层次遍历)
每弹出一个节点就统计一下…
参考代码3
//迭代法---层次遍历 时间:O(n) 空间:O(n) int countNodes(TreeNode* root) { if(root==NULL) { return 0; } queue<TreeNode*> Q; Q.push(root); int cnt = 0; while(!Q.empty()) { int size = Q.size(); for(int i = 0; i < size; i++) { cnt++; TreeNode* node = Q.front(); Q.pop(); if(node->left) { Q.push(node->left); } if(node->right) { Q.push(node->right); } } } return cnt; }
方法四:利用完全二叉树的性质
完全二叉树具有两种情况
- ①:满二叉树.
- ②最后一层叶子节点没有满
对于情况一:可以用2^(树深度-1)来计算.默认根节点深度为1
对于情况二:分别递归左孩子,右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后按照情况一来计算.
完全二叉树（一）如图：
完全二叉树（二）如图：
递归三要素:
- 确定参数和返回值:参数就是传入树的根节点,返回值就是以该节点为根节点二叉树的节点数量
确定结束条件:如果节点为空,就返回0,表示节点数为0.
确定单层递归的逻辑:先求左子树的高度,再求右子树的高度.如果两个高度相等,则说明是满二叉树,使用情况一的公式.如果不相等,则左右子树分别继续递归,最后再将递归后的结果返回.
参考代码4
int countNodes(TreeNode* root) { if(root==nullptr){ return 0; } TreeNode* left = root->left; TreeNode* right = root->right; int leftHeight = 0,rightHeight = 0;//左右子树的最小深度. while(left){ left=left->left; leftHeight++; } while(right){ right = right->right; rightHeight++; } if(leftHeight==rightHeight){ return (2<<leftHeight)-1; } return countNodes(root->left)+countNodes(root->right)+1; }
110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true
思路分析
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
本题要求比较高度,所以采用后序.
递归三部曲:
- 参数和返回值:参数为当前传入的节点,返回值:以当前传入节点为根节点的树的高度
- 结束条件 如果节点为NULL,返回0,表示以当前节点为根节点的树高度为0.
- 递归单层逻辑:求左子树的高度,求右子树的高度,如果高度之差>1则返回-1,否则返回左右子树高度的最大值+1.
参考代码
//递归法 int getHeight(TreeNode* node) { if(node==NULL) { //结束条件 return 0; } int leftHeight = getHeight(node->left);//求左子树深度 if(leftHeight==-1) {//如果子树不满足高度之差<=1则直接返回-1 return -1; } int rightHeight = getHeight(node->right);//右子树深度 if(rightHeight==-1) { return -1; } return abs(leftHeight-rightHeight) > 1 ? -1 : max(leftHeight,rightHeight)+1;//判断左右字数高度之差,如果>1则返回-1,否则返回其高度. } bool isBalanced(TreeNode* root) { if(root==NULL){ return true; } return getHeight(root)==-1 ? false: true; }
