104.二叉树的最大深度
题目链接:104. 二叉树的最大深度 - 力扣(LeetCode)n叉树也一样
思路:我的普通递归方法
class Solution {
public:
int depth(TreeNode* node,int d){
int l=0,r=0;
if(node->left==NULL&&node->right==NULL) return d;
if(node->left)l=depth(node->left,d+1);
if(node->right)r=depth(node->right,d+1);
return max(l,r);
}
int maxDepth(TreeNode* root) {
if(root==NULL)return 0;
return depth(root,1);
}
};
真是太简洁了
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
作者:力扣官方题解
链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/349250/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
111.二叉树的最小深度
题目链接:111. 二叉树的最小深度 - 力扣(LeetCode)
思路:显然本题和上一题思路不是很一致,因为根节点的子节点空缺和普通节点的子节点空缺是两种情况,这里参考官网做法。
错误做法:
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==NULL)return 0;
return min(minDepth(root->left),minDepth(root->right))+1;
}
};
事实上,只有左右节点皆为空,才叫叶子节点。
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);
}
};
222.完全二叉树的节点个数
题目链接:222. 完全二叉树的节点个数 - 力扣(LeetCode)
思路:自己根据第一题仿造出来的比较暴力的递归,没有利用完全二叉树的性质。
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL)return 0;
return countNodes(root->left)+countNodes(root->right)+1;
}
};
标签:node,return,int,随想录,二叉树,深度,NULL,root From: https://www.cnblogs.com/Liubox/p/18012242