郓城做网站,开发网络新技术的平台,网站改版的前端流程,企业密信app下载安装一、二叉树最大深度
最大深度#xff1a;根节点到最远叶子节点的最长路径上的节点数。
可以使用迭代法和递归法#xff0c;以递归法为例#xff1a;还是以递归三要素为基准#xff0c;进行解决。
int maxDepth(struct TreeNode* root) {// struct TreeNode** NodeList …一、二叉树最大深度
最大深度根节点到最远叶子节点的最长路径上的节点数。
可以使用迭代法和递归法以递归法为例还是以递归三要素为基准进行解决。
int maxDepth(struct TreeNode* root) {// struct TreeNode** NodeList (struct NoTreeNodede**)malloc(sizeof(struct Node*) * 100000);// int queue_left 0, queue_right 0;//一个用于对头移动一个用于队尾 index// NodeList[queue_right] root;// int queue_size 0;// /**这个用来保存每层多少个value**/// int index 0;// int *returnSize index;// if(root NULL)// {// return NULL;// }// int depth 0;// while(queue_right queue_left)//队列不为空// {// queue_size queue_right - queue_left;//获取当前queue size// //printf(size is %d L%d, R%d\n, queue_size, queue_left, queue_right);// //struct Node* preNode (struct Node*)malloc(sizeof(struct Node));// while(queue_size 0)// {// /**需要保存当前节点**/// struct TreeNode* curNode NodeList[queue_left];// /**队列indx往前进一**/// queue_left;// /**该节点的左右子节点入队列***/// if(curNode-left)// NodeList[queue_right] curNode-left;// if(curNode-right)// NodeList[queue_right] curNode-right;// queue_size--;// }// depth;// //result[(*returnSize)] Arr;//多少行就多少个数组// }// return depth;//递归法if(root NULL)return 0;int len_left maxDepth(root-left);int len_right maxDepth(root-right);return 1 (len_left len_right? len_left : len_right);
}
迭代法可参考上一篇。
二、二叉树最小深度
使用层序遍历的方式依旧可以解决参考上一篇博客。
递归法这里需要理清楚最小深度的定义特别这样的情况如果左子树或者右子树为空时候最小的深度不是止步在为空的节点处还是得看右边或者左边还有子树没有继续找。如果左子树为空右子树不为空说明最小深度是 1 右子树的深度。
/**最短距离的几种情况1 如果是满二叉树那么每个节点都有值那么深度就是最短的2 如果某一节点的子节点没有1左子节点没有2右子节点没有 3左右子节点没有**/
int minDepth(struct TreeNode* root) {// struct TreeNode** NodeList (struct NoTreeNodede**)malloc(sizeof(struct Node*) * 100000);// int queue_left 0, queue_right 0;//一个用于对头移动一个用于队尾 index// NodeList[queue_right] root;// int queue_size 0;// /**这个用来保存每层多少个value**/// int index 0;// int *returnSize index;// if(root NULL)// {// return 0;// }// int depth 0;// while(queue_right queue_left)//队列不为空// {// queue_size queue_right - queue_left;//获取当前queue size// //printf(size is %d L%d, R%d\n, queue_size, queue_left, queue_right);// //struct Node* preNode (struct Node*)malloc(sizeof(struct Node));// bool left_flg false;// bool right_flg false;// while(queue_size 0)// {// /**需要保存当前节点**/// struct TreeNode* curNode NodeList[queue_left];// left_flg false;// right_flg false;// /**队列indx往前进一**/// queue_left;// /**该节点的左右子节点入队列***/// if(curNode-left)// NodeList[queue_right] curNode-left;// else// left_flg true; // if(curNode-right)// NodeList[queue_right] curNode-right;// else// right_flg true;// if(left_flg right_flg)// {// break; // }// queue_size--;// }// depth;// //printf(depth %d\n, depth);// if(left_flg right_flg)// {// break; // }// }// return depth ;//递归法if(root NULL)return 0;int left_len minDepth(root-left);int right_len minDepth(root-right);//如果左子树不为空右子树空深度是左子树len 1if(root-left !root-right){return left_len 1;}if(!root-left root-right){return right_len 1;}return 1 (left_len right_len? left_len : right_len);
}
三、完全二叉树的节点个数
递归法依然按照递归三要素进行解答
int countNodes(struct TreeNode* root) {//递归法if(root NULL){return 0;} int left_num countNodes(root-left);int right_num countNodes(root-right);return 1 left_num right_num;
}
迭代法可以使用层次遍历的思路解答按照每一层遍历记录一个size ,每一层遍历结束后把每一层遍历结果相加。
int maxDepth(struct TreeNode* root) {struct TreeNode** NodeList (struct NoTreeNodede**)malloc(sizeof(struct Node*) * 100000);int queue_left 0, queue_right 0;//一个用于对头移动一个用于队尾 indexNodeList[queue_right] root;int queue_size 0;/**这个用来保存每层多少个value**/int index 0;int *returnSize index;if(root NULL){return NULL;}int depth 0;while(queue_right queue_left)//队列不为空{queue_size queue_right - queue_left;//获取当前queue size//printf(size is %d L%d, R%d\n, queue_size, queue_left, queue_right);//struct Node* preNode (struct Node*)malloc(sizeof(struct Node));while(queue_size 0){/**需要保存当前节点**/struct TreeNode* curNode NodeList[queue_left];/**队列indx往前进一**/queue_left;/**该节点的左右子节点入队列***/if(curNode-left)NodeList[queue_right] curNode-left;if(curNode-right)NodeList[queue_right] curNode-right;queue_size--;}depth;//result[(*returnSize)] Arr;//多少行就多少个数组}return depth;
}
