代码随想录算法训练营第19天 |104. 二叉树的最大深度 | 111. 二叉树的最小深度

代码随想录算法训练营第19天 |104. 二叉树的最大深度 | 111. 二叉树的最小深度 | 222. 完全二叉树的节点个数

本文主要是介绍代码随想录算法训练营第19天 |104. 二叉树的最大深度 | 111. 二叉树的最小深度 | 222. 完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

104. 二叉树的最大深度

题目链接

解：递归

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int get_depth(struct TreeNode *node) {if (node == NULL) return 0;int left = get_depth(node->left);int right = get_depth(node->right);int depth = 1 + (left > right ? left : right);return depth;
}int maxDepth(struct TreeNode* root) {return get_depth(root);
}

解: 层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/struct queue {int front, back;struct TreeNode *array[10000];
};int levelorder(struct TreeNode *root) {struct queue *que = (struct queue *)malloc(sizeof(*que));int depth = 0;struct TreeNode *node = root;memset(que, 0, sizeof(*que));que->front = que->back = 0;if (root == NULL) return depth;que->array[que->back++] = node;while (que->front != que->back) {int cur = que->back;while (que->front != cur) {node = que->array[que->front++];if (node->left != NULL) que->array[que->back++] = node->left;if (node->right != NULL) que->array[que->back++] = node->right;}depth++;}return depth;
}int maxDepth(struct TreeNode* root) {return levelorder(root);
}

559. N 叉树的最大深度

题目链接

解

/*** Definition for a Node.* struct Node {*     int val;*     int numChildren;*     struct Node** children;* };*/struct queue {int front, back;struct Node *array[10000];
};int levelorder(struct Node *root) {struct queue *que = (struct queue *)malloc(sizeof(*que));int depth = 0;struct Node *node = root;memset(que, 0, sizeof(*que));que->front = que->back = 0;if (root == NULL) return depth;que->array[que->back++] = node;while (que->front != que->back) {int cur = que->back;while (que->front != cur) {node = que->array[que->front++];for (int i = 0; i < node->numChildren; i++) {if (node->children[i] != NULL) que->array[que->back++] = node->children[i];}}depth++;}return depth;
}int maxDepth(struct Node* root) {return levelorder(root);
}

111. 二叉树的最小深度

题目链接

解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int get_depth(struct TreeNode *node) {if (node == NULL) return 0;int left = get_depth(node->left);int right = get_depth(node->right);if (node->left == NULL && node->right != NULL) return 1 + right;if (node->right == NULL && node->left != NULL) return 1 + left;return 1 + (left < right ? left : right);
}int minDepth(struct TreeNode* root) {return get_depth(root);
}

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

解: 递归

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int getnode(struct TreeNode *node) {if (node == NULL) return 0;int left = getnode(node->left);int right = getnode(node->right);return 1 + left + right;
}int countNodes(struct TreeNode* root) {return getnode(root);
}

解: 层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/struct queue {int front, back;struct TreeNode *array[100000];
};int countNodes(struct TreeNode* root) {struct queue *que = (struct queue *)malloc(sizeof(*que));int num = 0;struct TreeNode *node = root;memset(que, 0, sizeof(*que));que->front = que->back = 0;if (node == NULL) return num;que->array[que->back++] = node;while (que->front != que->back) {int cur = que->back;num += que->back - que->front;while (cur != que->front) {node = que->array[que->front++];if (node->left) que->array[que->back++] = node->left;if (node->right) que->array[que->back++] = node->right;}}return num;
}