【代码随想录37期】Day16 二叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数

本文主要是介绍【代码随想录37期】Day16 二叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的最大深度

v1.0:迭代法
/*** 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) {int max_depth = 0;if(root==nullptr)return max_depth;queue<TreeNode*> q;q.push(root);while(!q.empty()){int size = q.size();if(size > 0)max_depth++;for(int i = 0; i < size; i++){TreeNode* cur = q.front();q.pop();if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);}}return max_depth;}
};

int ret;void traversal(TreeNode* cur, int depth)
{if (cur == nullptr)return;ret = depth > ret ? depth : ret;traversal(cur->left, depth + 1);traversal(cur->right, depth + 1);
}int calculateDepth(TreeNode* root) {traversal(root, 1);return ret;
}

注意depth不好直接作为返回值，使用全局变量ret替代之

二叉树的最小深度

v1.0:递归法
/*** 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 min_depth = INT_MAX;void traversal(vector<vector<TreeNode*>>& treeNodes, TreeNode* cur, int depth){if(cur==nullptr)return;if(treeNodes.size()==depth)treeNodes.push_back(vector<TreeNode*>());treeNodes[depth].push_back(cur);if(cur->left==nullptr && cur->right==nullptr &&depth<min_depth)min_depth = depth+1;traversal(treeNodes, cur->left, depth+1);traversal(treeNodes, cur->right, depth+1);}int minDepth(TreeNode* root) {if(root==nullptr)return 0;vector<vector<TreeNode*>> treeNodes;int depth = 0;traversal(treeNodes, root, depth);return min_depth;}
};

int ret = INT32_MAX;
void traversal(TreeNode* cur, int depth)
{if (!cur)return;if(cur && !cur->left && !cur->right)ret = ret > depth ? depth : ret;traversal(cur->left, depth + 1);traversal(cur->right, depth + 1);
}int minDepth(TreeNode* root) {if (root == nullptr)return 0;traversal(root, 1);return ret;
}

完全二叉树的节点个数

int ret = 0;
void traversal(TreeNode* cur)
{if (!cur)return;ret++;traversal(cur->left);traversal(cur->right);
}int countNodes(TreeNode* root) {if (root == nullptr)return 0;traversal(root);return ret;
}