代码随想录笔记|C++数据结构与算法学习笔记-二叉树(四)|LeetCode222.完全二叉树的结点个数、110.平衡二叉树、257.二叉树的所有路径

本文主要是介绍代码随想录笔记|C++数据结构与算法学习笔记-二叉树(四)|LeetCode222.完全二叉树的结点个数、110.平衡二叉树、257.二叉树的所有路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

完全二叉树的结点个数
- 思路
- - 普通二叉树的解法
  - 完全二叉树的思路
- 伪代码实现
- CPP代码实现
平衡二叉树
- 思路
- - 遍历顺序
- 伪代码实现
- CPP代码实现
二叉树的所有路径
- 思路和遍历顺序
- 为什么会有回溯
- 伪代码实现
- CPP代码实现

完全二叉树的结点个数

力扣题目链接

文章链接：完全二叉树的结点个数

思路

普通二叉树的解法

确定遍历方法：后序遍历

确定递归的返回值和参数

int getNum(node){}

确定终止条件

if (node == NULL) return 0;

单层递归的逻辑

leftnum = getNum(node->left);
rightnum = getNum(node->right);
result = leftNum + rightnum + 1;
return result;

精简代码后：

return getNum(left) + getNum(right) + 1;

完全二叉树的思路

本题既然叫做完全二叉树的结点个数，那么他肯定是利用二叉树的特性来总结出结点数量。

完全二叉树的定义：除了底层结点，上面的结点都是满的，底层结点是从左到右依次排开的

我们可以把完全二叉树和满二叉树结合起啦进行解题。如果是满二叉树，深度为 $n$ ，其结点个数就是 $2^n- 1$ 。

所以如果我们可以知道根结点的子树如果是个满二叉树，我们就直接用公式来计算。

那么就引出了以下关键问题：

如何判断其子树是满二叉树。
并且同时求它的深度呢？

如果它是满二叉树，那就说明向左遍历的深度和向右遍历的深度一定是相等的。并且，最后的叶子结点左右遍历后中间肯定存在着叶子结点，而不会是空的，这是完全二叉树为我们保证的。如果左右遍历的深度不相等，那肯定就不是满二叉树了，关于这一点可以画图确认。

这里的思路非常严谨，建议直接去看视频：要理解普通二叉树和完全二叉树的区别！ | LeetCode：222.完全二叉树节点的数量

这个方法避免了我们取遍历一些中间的、没有必要去遍历的结点，因为完全二叉树为我们保证的。

伪代码实现

确定返回值和参数

int getNum(node){}

确定终止条件:遇到结点为空的情况；遇到子树为满二叉树的情况，我们要把子树的结点数量返回上去，所以我们遇到的子树是不是满二叉树，这个逻辑是写在终止条件里的

if(node == NULL) return 0;
left = node->left;//指向结点的左侧，左侧遍历计算左侧深度
right = node->right;//指向结点的右侧，右侧遍历计算右侧深度
leftdepth = 0; rightdepth = 0;
//左侧遍历统计左侧深度
while(left){left = left->left;leftdepth++;
}
//右侧遍历统计右侧深度
while(right){right = right->right;rightdepth++;
}
if (leftdepth == rightdepth)//左侧深度和右侧深度相等，说明是满二叉树return (2<<leftdepth) - 1;

单层递归的逻辑

leftnum = getNum(node->left);//左
rightnum = getNum(node->right);//右
result = leftnum + rightnum + 1;//中
return result;

CPP代码实现

// 普通二叉树
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);//精简//int countNodes(TreeNode* root) {//    if (root == NULL) return 0;//   return 1 + countNodes(root->left) + countNodes(root->right);//}}
};

//完全二叉树
class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便while (left) {  // 求左子树深度left = left->left;leftDepth++;}while (right) { // 求右子树深度right = right->right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0}return countNodes(root->left) + countNodes(root->right) + 1;}
};

平衡二叉树

力扣题目链接

后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树

平衡二叉树：左右子树的高度差小于等于1

思路

总体的思路就是判断每一个结点的左右子树的高度，看它的高度差是否超过1.

遍历顺序

求高度的话一定要用后序遍历；求深度要用前序遍历。

伪代码实现

参数和返回值

int getHeight(node)

确定终止条件：如果一个结点的左右子树的高度差超过了1，说明已经不是平衡二叉树了，那么当我们发现任何一个结点的左右孩子的高度不符合我们平衡二叉树的条件，我们就不返回这个结点的高度了，而是直接返回-1。

if (node == NULL) return 0;

单层递归逻辑

//左右子树不符合高度差小于1的情况
//左
leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
//右
rightHeight = getHeight(node->right);
if(rightHeight == -1) return -1;
int result;
//中
if(abs(rightHeight - leftHeight) > 1) result = -1;
else result = 1 + max(rightHeight, leftHeight);//左右子树的最大高度+父结点本身的高度等于当前结点的最大高度
return result;

CPP代码实现

class Solution {
public:// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1int getHeight(TreeNode* node) {if (node == NULL) {return 0;}int leftHeight = getHeight(node->left);if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right);if (rightHeight == -1) return -1;return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}
};

二叉树的所有路径

思路和遍历顺序

求路径的过程中我们一般要使用前序遍历，因为只有前序遍历我们才能让父结点去指向它的孩子结点，这样才能吧我们的顺序按照题目输出出来。这里的遍历顺序肯定前序遍历。

为什么会有回溯

其实回溯的过程往往就在递归的下面。

本题我们是要收集路径，加入有一个容器从根结点出发收集路径1，那么等到收集路径2的时候我们还要弹出路径1，只剩下一个根结点在里面，这就是回溯的过程。

伪代码实现

参数和返回值

void traversal(TreeNode* node, vector<int>& path, vector<string>& result){}

确定终止条件

if (node->left == NULL && node->right == NULL){result.push_back(path);
}

确定单层递归逻辑

//本题中，遍历中间结点的逻辑要写到前面来,因为我们的终止条件是到根结点的叶子结点就结束了，那就得return
//中
path.push_back(node->val);
if (node->left == NULL && node->right == NULL){result.push_back(path); return;
}
//左
if (node->left){traversal(node->left, path, result);path.pop_back(); 
}
//右
if (node->right){traversal(node->right, path, result);path.pop_back();
}

CPP代码实现

class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur->left == NULL && cur->right == NULL) {string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};//精简版本
class Solution {
private:void traversal(TreeNode* cur, string path, vector<string>& result) {path += to_string(cur->val); // 中if (cur->left == NULL && cur->right == NULL) {result.push_back(path);return;}if (cur->left) traversal(cur->left, path + "->", result); // 左if (cur->right) traversal(cur->right, path + "->", result); // 右}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;string path;if (root == NULL) return result;traversal(root, path, result);return result;}
};