222. 完全二叉树的节点个数
思路一：普通二叉树
递归法
求解二叉树的节点个数，可以将问题分解为求左子树的节点个数和右子树的节点个数，再求和
class Solution {private:int getNodesNum(TreeNode* cur) {if (cur == 0) 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);}};
代码精简后：
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(logn)，算上了递归系统栈占用的空间
迭代法
class Solution { public: int countNodes(TreeNode* root) { queue<TreeNode*> que; if (root == nullptr) return 0; que.push(root); int count = 0; while (!que.empty()) { int size = que.size(); // 当前层的节点个数 count += size; for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); if (node->left != nullptr) que.push(node->left); if (node->right != nullptr) que.push(node->right); } } return count; } };
思路二：完全二叉树
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
如何判断一个数是不是满二叉树：遍历到树的最左端，记录一个深度，遍历到最右端，记一个深度，如果两个深度相同，那么就是满二叉树
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
// 左节点一直往左，右节点一直往右，如果是满二叉树，就可以用2^n - 1来计算节点哥舒翰
int lLen = 0, rLen = 0;
while (left) {
left = left->left;
++lLen;
}
while (right) {
right = right->right;
++rLen;
}
if (rLen == lLen) {
return (2 << lLen) - 1; // 相当于 2^(len + 1) - 1, len 为子树的深度，总的树高应为 len + 1
}
// 如果不是子树不是满二叉树，那么递归处理左右子树，早晚得碰到满二叉树（最差的情况子树一个节点）
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
- 时间复杂度：O(logn * logn)
- 空间复杂度：O(logn)
110. 平衡二叉树
递归法
自底向上递归
- 明确返回值和参数
参数为传入的节点指针，返回值要返回传入节点为根节点树的深度。
那么如何标记左右子树是否差值大于1呢。
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
int getDepth(TreeNode* node)
明确终止条件：遇到空节点终止，返回0，表示当前节点为根结点时，树的高度为0
if (!node) return 0;明确单层递归的逻辑
判断是否为平衡二叉树，要考虑左右子树的高度差，如果差值小于1，则返回当前二叉树的高度，否则返回-1，表示不是平衡二叉树
int leftDepth = depth(node->left); // 左
if (leftDepth == -1) return -1;
int rightDepth = depth(node->right); // 右
if (rightDepth == -1) return -1;
int result;
if (abs(leftDepth - rightDepth) > 1) { // 中
result = -1;
} else {
result = 1 + max(leftDepth, rightDepth); // 以当前节点为根节点的最大高度
}
return result;
代码精简后：
int leftDepth = getDepth(node->left);
if (leftDepth == -1) return -1;
int rightDepth = getDepth(node->right);
if (rightDepth == -1) return -1;
return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
getDepth的整体代码
int getDepth(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftDepth = getDepth(node->left);
if (leftDepth == -1) return -1;
int rightDepth = getDepth(node->right);
if (rightDepth == -1) return -1;
return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
}
本题的完整代码：
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1
int getDepth(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftDepth = getDepth(node->left);
if (leftDepth == -1) return -1; // 说明左子树已经不是二叉平衡树
int rightDepth = getDepth(node->right);
if (rightDepth == -1) return -1; // 说明右子树已经不是二叉平衡树
return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
}
bool isBalanced(TreeNode* root) {
return getDepth(root) == -1 ? false : true;
}
};
class Solution {
public:
int dfs(TreeNode* root) {
if (root == NULL) return 0;
int left = dfs(root->left);
int right = dfs(root->right);
if (left == -1 || right == -1 || abs(left - right) > 1)
return -1;
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
return dfs(root) == -1 ? false : true;
}
};
自顶向下递归
class Solution {
public:
int getHeight(TreeNode* root) {
if (root == nullptr) return 0;
return max(getHeight(root->left), getHeight(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) return true;
return abs(getHeight(root->left) - getHeight(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
};
迭代法
此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。
虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。
因为对于回溯算法已经是非常复杂的递归了，如果在用迭代的话，就是自己给自己找麻烦，效率也并不一定高。
本题的迭代方式可以先定义一个函数，专门用来求高度。
这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的最大深度来求的高度）
代码如下：
// cur节点的最大深度，就是cur的高度
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != NULL) st.push(cur);
int depth = 0; // 记录深度
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node); // 中
st.push(NULL);
depth++;
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
depth--;
}
result = result > depth ? result : depth;
}
return result;
}
然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合，代码如下：
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) 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;
}
整体代码：
class Solution {
private:
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != NULL) st.push(cur);
int depth = 0; // 记录深度
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node); // 中
st.push(NULL);
depth++;
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
depth--;
}
result = result > depth ? result : depth;
}
return result;
}
public:
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) 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;
}
};
若有收获，就点个赞吧
0 人点赞
