目录
状态:递归AC,迭代套模板AC
根节点的高度就是二叉树的最大深度,所以用后序遍历求的根节点高度来求的二叉树最大深度
- class Solution {
- public:
- int getdepth(TreeNode*node) {
- if(node==0) 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);
- }
- };
参照二叉树层序遍历的模板来解决
- class solution {
- public:
- int maxDepth(TreeNode* root) {
- if (root == NULL) return 0;
- int depth = 0;
- queue
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 maxDepth(Node* root) {
- if (root == 0) return 0;
- int depth = 0;
- for (int i = 0; i < root->children.size(); i++) {
- depth = max (depth, maxDepth(root->children[i]));
- }
- return depth + 1;
- }
- };
- class solution {
- public:
- int maxDepth(Node* root) {
- queue
que; - if (root != NULL) que.push(root);
- int depth = 0;
- while (!que.empty()) {
- int size = que.size();
- depth++; // 记录深度
- for (int i = 0; i < size; i++) {
- Node* node = que.front();
- que.pop();
- for (int j = 0; j < node->children.size(); j++) {
- if (node->children[j]) que.push(node->children[j]);
- }
- }
- }
- return depth;
- }
- };
状态:递归AC,迭代没来得及做,需要注意
虽然看上去和最大深度类似,但是需要加入对节点是否是叶子节点的判断(左右孩子为空)。
- 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);
- }
- };
状态:递归AC,但是没有借助完全二叉树这一概念,所以还有改进的空间
迭代就是层序的时候每次出队列记录一下,递归和前面几题类似,也是后序遍历顺序
- 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);
- }
- };