二叉树的深度高度

104. 二叉树的最大深度

方法：递归(后序遍历)

class Solution {
private:int getDep(TreeNode*cur) {if (cur == NULL) return 0;int l = getDep(cur->left);int r = getDep(cur->right);int res = max(l, r) + 1;return res;}
public:int maxDepth(TreeNode* root) {return getDep(root);}
};

$时间复杂度O(n),空间复杂度O(h),h为树的高度

方法：递归(前序遍历)

class Solution {
private:int res;void getDep(TreeNode* cur, int dep) {res = res > dep ? res : dep;if (!cur->left && !cur->right) return;if (cur->left) getDep(cur->left, dep+1);if (cur->right) getDep(cur->right, dep+1);}
public:int maxDepth(TreeNode* root) {res = 0;if (root == NULL) return res;getDep(root, 1);return res;}
};

$时间复杂度O(n),空间复杂度O(h),h为树的高度

方法：bfs(层次遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> q;int dep = 0;if (root != NULL) q.push(root);while (!q.empty()) {int n = q.size();dep++;for (int i = 0; i < n; ++i) {TreeNode* nod = q.front();q.pop();if (nod->left) q.push(nod->left);if (nod->right) q.push(nod->right);}}return dep;}
};

$时间复杂度O(n),空间复杂度O(n)

111. 二叉树的最小深度

方法：递归(前序遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:int res;void getDep(TreeNode* cur, int dep) {if (!cur->left && !cur->right) {res = min(res, dep);return ;}if (cur->left) getDep(cur->left, dep+1);if (cur->right) getDep(cur->right, dep+1);return ;}
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;res = INT_MAX;getDep(root, 1);return res;}
};

$时间复杂度O(n),空间复杂度O(h),h为树的高度

方法：递归(后序遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {int getDep(TreeNode* nod) {if (nod == NULL) return 0;int l = getDep(nod->left), r = getDep(nod->right);if (nod->left == NULL && nod->right) return 1 + r;if (nod->right == NULL && nod->left) return 1 + l;int res = min(l, r) + 1;return res;}
public:int minDepth(TreeNode* root) {return getDep(root);}
};

$时间复杂度O(n),空间复杂度O(h),h为树的高度

方法：bfs(层次遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> q;if (root != NULL) q.push(root);int dep = 0;while (!q.empty()) {int n = q.size();++dep;for (int i = 0; i < n; ++i) {TreeNode* nod = q.front();q.pop();if (nod->left) q.push(nod->left);if (nod->right) q.push(nod->right);if (!nod->left && !nod->right) return dep;}}return dep;}
};

$时间复杂度O(n),空间复杂度O(n)

222. 完全二叉树的节点个数

方法：递归

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:int now = 0;int getVal(TreeNode* cur) {if (cur == NULL) return 0;int l =  getVal(cur->left);int r = getVal(cur->right);int now = l + r + 1;return now;}
public:int countNodes(TreeNode* root) {if (root == NULL) return 0;return getVal(root);}
};

$时间复杂度O(n),空间复杂度O(h),h为树的高度

方法：bfs(层次遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {queue<TreeNode*> q;if (root != NULL) q.push(root);int res = 0;while (!q.empty()) {int n = q.size();res += n;for (int i = 0; i < n; ++i) {TreeNode* nod = q.front();q.pop();if (nod->left) q.push(nod->left);if (nod->right) q.push(nod->right);}}return res;}
};

$时间复杂度O(n),空间复杂度O(n)