今日刷题重点—二叉树的深度
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。
方法一:递归(后序)
递归三要素:
参数和返回值:参数就是树的根节点,返回值:树的深度
结束条件:如果为空节点NULL，就返回0，表示高度为0
单层递归逻辑:先求左子树的深度,再求右子树的深度,最后取左右深度的最大值,再+1(因为要算上当前的节点),返回的就是以目前节点为根节点的树的深度.
参考代码1
int maxDepth(TreeNode* root) {//参数为要判断层数的节点 if(root==NULL) { //结束条件 return 0; } int leftDepth = maxDepth(root->left);//每次继续递归计算左子树的深度 int rightDepth = maxDepth(root->right);//计算右子树的深度 int depth = 1 + max(leftDepth,rightDepth);//寻找最大的然后加上当前层便是到当前节点的深度. return depth;//返回给上一层. }
方法二:递归(先序)
使用一个变量记录每一层递归过程中树的最大深度,最后进行返回.
递归三要素:
参数和返回值:参数就是树的根节点 root 和 从根节点到当前节点的深度depth.
结束条件:当遇到叶子节点时就不需要往下递归了.
单层递归逻辑: 如果根节点的左子树不为空,则继续进行递归,同时传入的depth+1 . 左子树递归完毕后,进行右子树的递归…
参考代码2
//递归法:先序 int result; void getDepth(TreeNode* node,int depth){//depth:表示到root为止,树的深度. result = depth>result ? depth : result; //进来该函数之后先更新result; if(node->left==NULL&&node->right==NULL){//判断左右节点是否为空 return; } if(node->left){ depth++; getDepth(node->left,depth); depth--;//进行回溯 用于下面右子树的递归判断. } if(node->right){ // depth++; // getDepth(node->right,depth); // depth--; getDepth(node->right,depth+1); } return; } int maxDepth(TreeNode* root) { result = 0; if(root==NULL) { return 0; } getDepth(root,1); return result; }
方法三—迭代法(层次遍历)
采用队列一层层的进行遍历,每次depth++.
这种方法写起来和理解起来最佳
参考代码3
//方法三:层次遍历(最好理解.) int maxDepth(TreeNode* root) { if(root==NULL){ return 0; } queue<TreeNode*> Q; Q.push(root); int depth = 0; while(!Q.empty()){ int size = Q.size(); for(int i = 0;i < size;i++){ TreeNode* node = Q.front(); Q.pop(); if(node->left){ Q.push(node->left); } if(node->right){ Q.push(node->right); } } depth++;//每遍历一层depth++ } return depth; }
559. N 叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5
思路分析:
N叉树只是 父节点上的子节点有多个,其他的和二叉树处理思路相同.
参考代码1—递归(后序)
//递归 后序.. int maxDepth(Node* root) { if(root==NULL) { return 0; } int depth,maxdepth = 0; for(int i = 0; i < root->children.size(); i++) { depth = maxDepth(root->children[i]);//获取到当前子节点的深度. maxdepth = max(depth,maxdepth);//进行更新. } return maxdepth+1;//返回给上一层 到当前节点的深度. }
参考代码2—递归(先序)
//递归,先序. int result; void getDepth(Node* node,int depth) { result = depth > result ? depth : result; for(int i = 0; i < node->children.size(); i++) { if(node->children[i]) { getDepth(node->children[i],depth+1); } } return; } int maxDepth(Node* root) { result = 0; if(root==NULL) { return 0; } getDepth(root,1); return result; }
参考代码3—迭代(层次遍历)
//迭代:层次遍历 int maxDepth(Node* root) { if(root==NULL){ return 0; } queue<Node*> Q; Q.push(root); int depth = 0; while(!Q.empty()){ int size = Q.size(); for(int i = 0;i < size;i++){ Node* node = Q.front(); Q.pop(); for(int j = 0;j < node->children.size();j++){ if(node->children[j]){ Q.push(node->children[j]); } } } depth++; } return depth; }
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
方法一—递归(后序)
求最小深度时,因为是遍历到叶子节点才算一个深度.我们不可以直接在最大深度的算法上仅仅把返回值从max改成min就OK了.
如果那样的话,会出现如下: 算法求出的最小深度是1,但实际上是3
所以我们在处理时要注意节点左子树和右子树,一个为空一个不为空的特殊情况.
- 当左子树为空右子树不为空时,返回的应该是右子树深度+1;
- 当右子树为空左子树不为空时,返回的应该是左子树深度+1;
- 当左右子树都不为空时,返回的是两棵树的最小深度+1;
参考代码1
//递归 int minDepth(TreeNode* root) { if(root==NULL) { return 0; } int leftDepth = minDepth(root->left); int rightDepth = minDepth(root->right); if(root->left==NULL&&root->right) { //当左子树为空,右子树不为空,则深度= 右子树深度+1 return rightDepth+1; } if(root->right==NULL&&root->left) { //当左子树不为空,右子树为空,则深度= 左子树深度+1 return leftDepth+1; } return 1+min(leftDepth,rightDepth);//都不为空,则取最小的那个. }
方法二—迭代法(层次遍历)
一遇到叶子节点就返回深度.
参考代码2
//层次遍历 int minDepth(TreeNode* root) { if(root==NULL){ return 0; } queue<TreeNode*> Q; Q.push(root); int depth = 0; while(!Q.empty()){ int size = Q.size(); for(int i = 0;i < size;i++){ TreeNode* node = Q.front(); Q.pop(); if(node->left){ Q.push(node->left); } if(node->right){ Q.push(node->right); } if(!node->left&&!node->right){ return depth+1;//带上当前层.. } } depth++; } return depth; }
