本文主要是介绍【代码随想录】【算法训练营】【第16天】 [104]二叉树的最大深度 [111]二叉树的最小深度 [222]完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
思路及算法思维，指路 代码随想录。
题目来自 LeetCode。
day 16，周四，再坚持一下吧~
题目详情
[104] 二叉树的最大深度
题目描述
104 二叉树的最大深度
解题思路
前提：二叉树的最大深度，等价于二叉树的层数，等价于求最底层二叉树叶子结点的高度。
思路：求二叉树深度：前序遍历；求二叉树高度：后序遍历；求二叉树层数：层级遍历。
重点：二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）；二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）。
代码实现
C语言
层级遍历 队列
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int maxDepth(struct TreeNode* root) {int ans = 0;// 判断树非空if (root == NULL){return ans;}// 层级遍历， 队列struct TreeNode *queue[10000];int idx = 0;queue[idx++] = root;int start = 0;while (start < idx){int levelCnt = idx - start;for (int i = 0; i < levelCnt; i++){struct TreeNode *cur = queue[start++];if (cur->left){queue[idx++] = cur->left;}if (cur->right){queue[idx++] = cur->right;}}ans++;}return ans;
}
后序遍历 求root的高度，递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int max(int a, int b)
{return (a > b) ? a : b;
}int hight(struct TreeNode* root)
{// 后序遍历求高度，最大深度即为root的高度if (root == NULL){return 0;}int leftHight = hight(root->left);int rightHight = hight(root->right);return 1 + max(leftHight, rightHight);
}int maxDepth(struct TreeNode* root) {// 后序遍历求高度，最大深度即为root的高度，递归return hight(root);
}
前序遍历 求root深度，递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int max(int a, int b)
{return (a > b) ? a : b;
}void depthFun(struct TreeNode* root, int depth, int *result)
{// 前序遍历求深度, 注意回溯的过程if (root == NULL){return ;}*result = max(*result, depth);depthFun(root->left, depth + 1, result);depthFun(root->right, depth + 1, result);return ;
}int maxDepth(struct TreeNode* root) {// 后序遍历求高度，最大深度即为root的高度，递归int result = 0;int depth = 0;depthFun(root, depth + 1, &result);return result;
}
[111] 二叉树的最小深度
题目描述
111 二叉树的最小深度
解题思路
前提：二叉树的最小深度，等价于二叉树最高层叶子结点的层数，等价于求二叉树最高层叶子结点的高度。
思路：求二叉树深度：前序遍历；求二叉树高度：后序遍历；求二叉树层数：层级遍历。
重点：注意叶子结点的含义: (node->left == NULL) && (node->right == NULL)。
代码实现
C语言
层序遍历，队列
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int minDepth(struct TreeNode* root) {int ans = 0;// 判断空树if (root == NULL){return ans;}// 层序遍历，队列struct TreeNode *queue[100000];int idx = 0;queue[idx++] = root;int start = 0;while (start < idx){int levelCnt = idx - start;ans++;for (int i = 0; i < levelCnt; i++){struct TreeNode *cur = queue[start++];// 判断是否为叶子结点if ((cur->left == NULL) && (cur->right == NULL)){// 找到第一个叶子结点，直接退出return ans;}if (cur->left){queue[idx++] = cur->left;}if (cur->right){queue[idx++] = cur->right;}}}return ans;
}
前序遍历深度，递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int minFun(int a, int b)
{return (a < b) ? a : b;
}void depthFun(struct TreeNode* root, int depth, int *result)
{if (NULL == root){return ;}// 寻找叶子结点if ((root->left == NULL) && (root->right == NULL)){*result = minFun(*result, depth);return ;}depthFun(root->left, depth + 1, result);depthFun(root->right, depth + 1, result);
}int minDepth(struct TreeNode* root) {// 判断空树if (root == NULL){return 0;}int ans = INT_MAX;// 前序遍历，递归depthFun(root, 1, &ans);return ans;
}
[222] 完全二叉树的节点个数
题目描述
222 完全二叉树的节点个数
解题思路
前提：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
思路：普通二叉树遍历；利用完全二叉树特性，拆解为n个满二叉树，利用 2^树深度 - 1 来计算。
重点：完全二叉树的特性。
代码实现
C语言
普通二叉树 先序遍历 递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/void travesal(struct TreeNode *root, int *ans)
{if (root == NULL){return ;}//先序遍历(*ans)++;travesal(root->left, ans);travesal(root->right, ans);
}int countNodes(struct TreeNode* root) {int ans = 0;travesal(root, &ans);return ans;
}
普通二叉树 结点数量 递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int countNodeNum(struct TreeNode *root)
{if (root == NULL){return 0;}int leftNum = countNodeNum(root->left);int rightNum = countNodeNum(root->right);return (leftNum + rightNum + 1);
}int countNodes(struct TreeNode* root) {int ans = countNodeNum(root);return ans;
}
完全二叉树分解成满二叉树，利用满二叉树结点数为2^n -1。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int countNodeNum(struct TreeNode *root)
{if (root == NULL){return 0;}int leftDepth = 0;int rightDepth = 0;struct TreeNode *left = root->left;struct TreeNode *right = root->right;// 求左侧叶子结点的深度while (left){leftDepth++;left = left->left;}// 求右侧叶子结点的深度while (right){rightDepth++;right = right->right;}// 判断是否为满二叉树, 两边深度相同// 注意：两侧深度相同的二叉树不是满二叉树，但两侧深度相同的完全二叉树，一定是满二叉树。if (leftDepth == rightDepth){return (2 << leftDepth) - 1;}int leftNum = countNodeNum(root->left);int rightNum = countNodeNum(root->right);return (leftNum + rightNum + 1);
}int countNodes(struct TreeNode* root) {int ans = countNodeNum(root);return ans;
}
今日收获
- 二叉树的深度、高度；
- 完全二叉树的特性。
这篇关于【代码随想录】【算法训练营】【第16天】 [104]二叉树的最大深度 [111]二叉树的最小深度 [222]完全二叉树的节点个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
