✨牛客刷题

• 🍑前言
• 🍑题目描述
• 🍑方法一(看成普通二叉树)
• • 🍊🍊 递归
  • 🍊🍊迭代
• 🍑方法二(利用完全二叉树的性质)
• 🍑结束语

📃个人主页: 不断前进的皮卡丘
🌞博客描述: 梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记
🔥网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备----- 刷题神器

🍑前言

学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站点此进入，里面还有大量的面经，大家可以在面试之前去看看

我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

🍑题目描述

完全二叉树的结点个数

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

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

🍊🍊 递归

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

🍊🍊迭代

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

很明显，题目都说了是完全二叉树，肯定是希望我们利用完全二叉树的性质来解答，不然的话，题目直接让我们求二叉树的结点个数就可以了。我们首先要对完全二叉树有所了解。
其实,完全二叉树可以有下面的几种情况


假设左子树高度为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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🍑结束语

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