[算法刷题笔记]二叉树练习(3)完全二叉树的节点个数

清疚 2024-04-21 08:01 71阅读 0赞

> #### ✨牛客刷题 ####
> 
>  *  ?前言
>  *  ?题目描述
>  *  ?方法一(看成普通二叉树)
>  *   *  ?? 递归
>      *  ??迭代
>  *  ?方法二(利用完全二叉树的性质)
>  *  ?结束语
> 
>   
> ?个人主页: [不断前进的皮卡丘][Link 1]  
> ?博客描述: **梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记**  
> **?网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备**\----- [刷题神器][Link 2]

## ?前言 ##

> 学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站[点此进入][Link 2]，里面还有大量的面经，大家可以在面试之前去看看  
> ![在这里插入图片描述][15ff82da90f44be2a95cb48c93105248.png]  
> 我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

## ?题目描述 ##

[完全二叉树的结点个数][Link 3]![在这里插入图片描述][0e0b0dce03d54c7e8138970c5dcd8645.png]

## ?方法一(看成普通二叉树) ##

> 如果我们把完全二叉树看成普通的二叉树的话，那么，求它的结点个数其实和求普通二叉树的结点个数的方法是一样的，如果根节点为空，则返回0，否则就遍历左子树和右子树，然后把左子树的结点个数和右子树的结点个数+1返回，就是最后的结果，我们可以用递归，也可以利用队列，进行遍历

### ?? 递归 ###

>public class Solution {
        
       public int nodeNum(TreeNode head) {
        
           if(head==null) return 0;
           return nodeNum(head.left)+nodeNum(head.right)+1;
       }
    }

### ??迭代 ###

class Solution {
        
        // 迭代法
        public int nodeNum(TreeNode head) {
        
            if (head == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(head);
            int result = 0;
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                while (size -- > 0) {
        
                    TreeNode cur = queue.poll();
                    result++;
                    if (cur.left != null) queue.offer(cur.left);
                    if (cur.right != null) queue.offer(cur.right);
                }
            }
            return result;
        }
    }

## ?方法二(利用完全二叉树的性质) ##

> 很明显，题目都说了是完全二叉树，肯定是希望我们利用完全二叉树的性质来解答，不然的话，题目直接让我们求二叉树的结点个数就可以了。`我们首先要对完全二叉树有所了解`。  
> 其实,完全二叉树可以有下面的几种情况  
> ![在这里插入图片描述][5a3f9c4e80b6433a9e9f0aafdb366e39.png]  
> ![在这里插入图片描述][5fb65c92520f493fa9ec8e7c5c7ba992.png]  
> 假设左子树高度为leftHeight,右子树高度为rightHeight  
> 1️⃣当左子树和右子树高度相同的时候，只能是情况③或情况④，不管是哪一个情况，左子树都是满二叉树  
> 2️⃣当左子树和右子树高度不同的时候，只能是情况①或②，不管是哪一个情况，右子树都是满二叉树  
> 3️⃣如果一棵树是满二叉树，我们有下面这个公式来求解它的结点个数，2^满二叉树的高度-1

public class Solution {
        
       public int nodeNum(TreeNode head) {
        
            if (head == null) return 0;
            int l = getHeight(head.left); // 求左树高
            int r = getHeight(head.right); // 求右树高
            
            if (l == r) return (1 << l) + nodeNum(head.right);
            
            else return (1 << r) + nodeNum(head.left);
        }
        // 求树高
        public int getHeight(TreeNode root) {
        
            int height = 0;
            while (root != null) {
        
                // 因为完全二叉树是基于左节点的 所以我们可以遍历到最深的左节点 此时的height就是树高
                root = root.left; 
                height++;
            }
            return height;
        }
    }

![在这里插入图片描述][934c3dc901464e6bafce1c758112e861.png]

## ?结束语 ##

> 希望大家可以自己动手练习一下，算法光看是不行的，必须亲自动手敲代码，有时候你会发现自己有思路，但是又写不出来，这就是缺乏练习的原因。大家平时在做题的时候，可以多思考，多总结。  
> 刚开始的时候，我们可能遇到一种新的题型，完全没有思路的时候，其实可以先去看看别人的思路，还有题解，把它理解下来，然后把代码敲出来(不要复制粘贴,我们根据自己的理解敲出代码这样才有效果，如果中途卡住了，也可以再回过头去看看)  
> 另外，为了检测一下我们是否真正的掌握，我们可以去做几道相似的题目巩固一下，顺便检验一下自己的成果。  
> [点此跳转去练习][Link 2]![在这里插入图片描述][5e96aa56fa7445e49d327faa99883c79.png]  
> 这里面有对应的题目，比如链表，二叉树等等，我们可以找到自己想要练习的题目，根据标签就可以进行筛选了，非常的方便。  
> 算法不是看会的，而是在做题中学会的，这是我的个人看法，刚开始由浅入深，不要太追求效率，先把自己的思路写出来，然后逐渐培养思维，然后在有一定的积累以后，我们再来追求效率，再来追求一题多解。算法贵在坚持，不可能一朝一夕就成为大牛。  
> 如果有的小伙伴急着找工作的话，如果时间比较紧张，那么，我们可以先把一些面试高频的题目给做了，像这里面就列举出来了面试必刷题目。  
> [一起坚持下去，冲冲冲][Link 2]![在这里插入图片描述][c25b6a6f7b15469da28ef58e5b87d303.png]

[Link 1]: https://blog.csdn.net/qq_52797170?spm=1010.2135.3001.5343
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_pkq_sf
[15ff82da90f44be2a95cb48c93105248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/eb48151e286b4223b33c958d8bd2e522.png
[Link 3]: https://www.nowcoder.com/practice/512688d2ecf54414826f52df4e4b5693?tpId=196&tqId=37120&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E5%25AE%258C%25E5%2585%25A8&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E5%AE%8C%E5%85%A8
[0e0b0dce03d54c7e8138970c5dcd8645.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/38009cb46a8542658158f24eab3c4dde.png
[5a3f9c4e80b6433a9e9f0aafdb366e39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/eeec53a394e74a098f6f6b2e1c05a186.png
[5fb65c92520f493fa9ec8e7c5c7ba992.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/63b7d58831e449708ef138b7da68eabd.png
[934c3dc901464e6bafce1c758112e861.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/2f5169f34263447686bb0232b51bbfaa.png
[5e96aa56fa7445e49d327faa99883c79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/05969c80d3cd43faa3e77e0c02fcab84.png
[c25b6a6f7b15469da28ef58e5b87d303.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/5ea66723fc6243d6a1532592867d4c6f.png