前言
算法的重要性不言而喻！区分度高！
现在学习的门槛低了，只有能上网每个人都可以学编程！培训班6个月就可以培养出来能干活的人，你怎么从这些人中脱颖而出？没错！就是学算法，学一些底层和基础的东西。
说的功利点是为了竞争，卷死对手。真心话说就是能提高自己的基础能力，为技术可持续发展做好充分的准备！！！
提前入门学习书籍：CPrimerPlus、大话数据结构
刷题网站
我是按照代码随想录提供的刷题顺序进行刷题的，大家也可以去刷leetcode最热200道，都可以
刷题嘛，最重要的就是坚持了！！！
画图软件
OneNote
这个要经常用，遇见不懂的流程的话就拿它画一画！
笔记软件
Typoral
题目
解析
对递归的图形方式解释 我们随便画了一个二叉树如下：
那么递归是怎么递归的呢？
我们可以知道递归三要素：
- 确定递归的参数和返回值
- 递归结束的条件
- 单层递归的逻辑
一般递归结束的条件就是该节点为空，好的那递归到那个节点的时候为空了呢？一般都是到叶子节点的时候开始相关计算，如下图：
我们拿这道题来举例：
计算过程
if (cur == NULL) return 0; int leftNum = getNodesNum(cur->left); // 左 int rightNum = getNodesNum(cur->right); // 右 int treeNum = leftNum + rightNum + 1; // 中 return treeNum;
代码解析：
- 判断指针到叶子结点了
- 此时leftNum和rightNum都为0，因为叶子结点已经没有子节点了
- 所以treeNum此时等于0+0+1 = 1
- 叶子节点计算完毕，在计算其他叶子节点
- 计算非叶子节点，同样也是上面的过程，我这里拿B节点举例，到计算B节点时treeNum = 1 + 1 +1 = 3
完整代码
// 版本一 class Solution { private: int getNodesNum(TreeNode* cur) { if (cur == NULL) return 0; int leftNum = getNodesNum(cur->left); // 左 int rightNum = getNodesNum(cur->right); // 右 int treeNum = leftNum + rightNum + 1; // 中 return treeNum; } public: int countNodes(TreeNode* root) { return getNodesNum(root); } };
以上为二叉树的通用解法，但题目是完全二叉树的节点个数。
哎，完全二叉树那就不一样了。 完全二叉树只有两种情况：
- 满二叉树
- 最后一层叶子节点没有满（节点集中在左侧）
满二叉树节点的个数为2^树深度 - 1
那么完全二叉树，可以递归左孩子和右孩子，递归到一定深度一定会有满二叉树，所以也可以用第一种情况来计算
利用完全二叉树的特性计算
1.如何去判断一个左子树或者右子树是不是满二叉树呢？
当递归左子树的深度等于右子树的深度，那就是满二叉树
if(root == null) { return 0; } int leftDepth = getDepth(root.left); int rightDepth = getDepth(root.right); if (leftDepth == rightDepth) {// 左子树是满二叉树 return (1 << leftDepth) + countNodes(root.right); } else {// 右子树是满二叉树 return (1 << rightDepth) + countNodes(root.left); }
画图理解代码
完整代码如下：
class Solution { /** * 针对完全二叉树的解法 * * 满二叉树的结点数为：2^depth - 1 */ public int countNodes(TreeNode root) { if(root == null) { return 0; } int leftDepth = getDepth(root.left); int rightDepth = getDepth(root.right); if (leftDepth == rightDepth) {// 左子树是满二叉树 // 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点 return (1 << leftDepth) + countNodes(root.right); } else {// 右子树是满二叉树 return (1 << rightDepth) + countNodes(root.left); } } private int getDepth(TreeNode root) { int depth = 0; while (root != null) { root = root.left; depth++; } return depth; } }
