二叉樹|104.二叉樹的最大深度绞绒、111.二叉樹的最小深度婶希、222.完全二叉樹的節(jié)點個數(shù)
104.二叉樹的最大深度
自己審題思路
使用層序遍歷計算最大深度（有多少層就有多深）
看完代碼隨想錄題解后的收獲
遞歸算法學習
代碼（迭代--層序遍歷）：
class solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++; // 記錄深度
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);
}
}
return depth;
}
};
代碼（遞歸）：
class solution {
public:
int getdepth(TreeNode* node) {
if (node == NULL) return 0;
int leftdepth = getdepth(node->left); // 左
int rightdepth = getdepth(node->right); // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;
}
int maxDepth(TreeNode* root) {
return getdepth(root);
}
};
參考詳解
111.二叉樹的最小深度
自己審題思路
使用層序遍歷榕暇，在判斷當前節(jié)點沒有左右孩子后返回蓬衡。
看完代碼隨想錄題解后的收獲
遞歸思路的學習。
代碼（迭代--層序遍歷）：
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++; // 記錄最小深度
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);
if (!node->left && !node->right) { // 當左右孩子都為空的時候彤枢，說明是最低點的一層了狰晚，退出
return depth;
}
}
}
return depth;
}
};
代碼（遞歸）：
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left); // 左
int rightDepth = getDepth(node->right); // 右
// 中
// 當一個左子樹為空，右不為空缴啡，這時并不是最低點
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
// 當一個右子樹為空壁晒，左不為空，這時并不是最低點
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
參考詳解
222.完全二叉樹的節(jié)點個數(shù)
自己審題思路
使用二叉樹遍歷业栅，遍歷到一個節(jié)點就
++秒咐；
看完代碼隨想錄題解后的收獲
使用完全二叉樹的特性來優(yōu)化算法谬晕；
代碼（迭代）
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
result++; // 記錄節(jié)點數(shù)量
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
代碼（遞歸）
// 版本一
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);
}
};
// 版本二
class Solution {
public:
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是有目的的，為了下面求指數(shù)方便
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;
}
};
上述算法時間復雜度為
logN*logN時間復雜度計算
