222、完全二叉树的节点个数
题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
思路
- 题目分析：
- 可以把完全二叉树分为两种情况：完全二叉树、满二叉树
- 若是满二叉树：则向左递归和向右递归获得的深度一样；直接用公式2depth-1计算节点个数
- 若是完全二叉树：向左向右递归知道遇到当前节点下的二叉树为满二叉树，然后根据公式计算节点个数后返回
- 递归法：
- 参数：root入口函数时代表根节点，递归中代表当前节点
- 返回值：int返回节点个数
- 终止条件：当前节点为空时，返回0；当前根节点所在二叉树为满二叉树时，用公式计算当前二叉树个数后返回。
- 递归逻辑：左右中
- 迭代法：
- 层序遍历：得到每一层的节点数，然后累加
- 数据结构：队列
代码
递归法:
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;
//判断以当前节点为根节点的二叉树是否为满二叉树
//得到左子树深度
while (left) {
left = left->left;
leftDepth++;
}
//得到右子树深度
while (right) {
right = right->right;
rightDepth++;
}
if (rightDepth == leftDepth) {
return (2 << leftDepth) - 1;//(2 << 1) 相当于2^2，因此leftDepth初始化为0;返回当前满二叉树的节点
}
//递归逻辑
return countNodes(root->left) + countNodes(root->right) + 1;//左 右 中
}
};
迭代法：
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> que;
que.push(root);
int sum = 0;
while (!que.empty()) {
int size = que.size();
int num = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
num++;
}
sum += num;
}
return sum;
}
};
110、平衡二叉树
题目描述
给定一个二叉树，判断它是否是 平衡二叉树
思路
- 题目分析：
- 判断二叉树是否为平衡二叉树：需要求以当前节点为根节点的树的左右子树的高度，然后比较它们之间的差是否大于1。
- 递归法：
- 参数：传入当前节点
- 返回值：int，如果以当前节点为根节点的二叉树是平衡二叉树，则返回当前二叉树的最大高度；如果不是平衡二叉树，返回-1。
- 终止条件：当前节点为空时，返回0；
- 递归逻辑：后序遍历，左右中
- 迭代法：
- 定义一个函数：求传入节点的高度
- 用栈模拟后序遍历：每个节点的高度就是以这个节点为根节点的树的最大深度
- 用栈模拟后序遍历：遍历每一个节点，求出每一个节点左右子树的高度，若高度大于1则返回false；否则，返回true。
代码
递归法：
class Solution {
public:
int getHeight(TreeNode* cur) {
if (cur == nullptr) return 0;
int leftHeight = getHeight(cur->left);//左子树高度
if (leftHeight == -1) return -1;
int rightHeight = getHeight(cur->right);//右子树高度
if (rightHeight == -1) return -1;
//子树最大高度加1 == 当前树的最大高度
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
迭代法：
class Solution {
public:
//节点的高度就是以节点为根节点的二叉树的最大深度
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != nullptr) st.push(cur);
int depth = 0;//记录深度
int res = 0;//用来返回的最大深度，也就是高度
while (!st.empty()) {
TreeNode* node = st.top();
if (node != nullptr) {
st.pop();
st.push(node);
st.push(nullptr);//标记
depth++;
if (node->right) st.push(node->right);//右
if (node->left) st.push(node->left);//左
} else {
st.pop();//去掉标记
//node = st.top();//取出节点
st.pop();
depth--;
}
res = res > depth ? res : depth;
}
return res;
}
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == nullptr) return true;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (abs(getDepth(node->left) - getDepth(node->right)) > 1) return false;
if (node->right) st.push(node->right);//右
if (node->left) st.push(node->left);//左
}
return true;
}
};
257、二叉树的所有路径
题目描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
思路
** 递归法**：
- 返回值：不需要返回值
- 参数：cur代表当前节点，
vector<int>类型的path用来存储路径上的节点，vector<string>类型的res用来当作路径结果返回。- 终止条件：遇到叶子节点。也就是
cur->left == null && cur->right == null。- 递归逻辑：前序遍历，中左右
- 回溯逻辑：每一次递归返回后都是一次回溯，应该把回溯前(递归返回前)遍历到的节点取出。
迭代法：
- 用前序遍历的方式来模拟遍历路径的过程。
- 数据结构：一个栈用来存储遍历到的节点；一个栈用来存储同步遍历过程的路径(当遇到叶子节点时栈顶元素为一条最终可用的路径)；一个
vector<string>类型的容器来存储最终的路径结果集- 随着遍历过程，一个栈存储遍历的节点，一个栈同步存储一条路径。
- 到达叶子节点的时候，栈中存储的路径已经是最终可用的一条路径，将这条路径加入结果集。
- 遍历过程中回退时，存储节点的栈和存储路径的栈要同时取出栈顶元素，达到回退效果。
代码
递归法：
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& res) {
path.push_back(cur->val);//中
//终止条件：遇到叶子节点
if (cur->left == nullptr && cur->right == nullptr) {//将一条字符串路径添加到结果集
string sPath;
for (int i = 0; i < path.size() - 1; i++) {
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
res.push_back(sPath);
return;
}
//左
if (cur->left) {
traversal(cur->left, path, res);
path.pop_back();//回溯
}
//右
if (cur->right) {
traversal(cur->right, path, res);
path.pop_back();//回溯
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<int> path;
vector<string> res;
if (root == nullptr) return res;
traversal(root, path, res);
return res;
}
};
迭代法：
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> treeSt;//用来保存遍历的节点
stack<string> pathSt;//用来保存一条路径，栈顶的元素是最终路径(根节点到当前节点的路径)
vector<string> result;//用来保存路径集
if (root == nullptr) return result;
treeSt.push(root);
pathSt.push(to_string(root->val));
while (!treeSt.empty()) {
TreeNode* node = treeSt.top(); treeSt.pop();//取出节点 中
string path = pathSt.top(); pathSt.pop();//取出该节点对应的路径
//当前节点叶子节点，当前路径也是一条可用的路径
if (node->left == nullptr && node->right == nullptr) {
result.push_back(path);
}
//右
if (node->right) {
treeSt.push(node->right);
pathSt.push(path + "->" + to_string(node->right->val));
}
//左
if (node->left) {
treeSt.push(node->left);
pathSt.push(path + "->" + to_string(node->left->val));
}
}
return result;
}
};
总结
- 节点的高度：从最下层节点到该节点的节点个数。
- 节点的深度：从根节点到该节点的节点个数。
- 求深度要从上往下查，用前序遍历(中左右)。
- 求高度要从下往上查，用后序遍历(左右中)。
