104. 二叉树的最大深度
题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
算法思想：
求最大深度，可以转化为求根节点的高度，根节点的高度等于左节点的高度，右节点的高度的最大值+1
后序遍历的处理逻辑是左右中。中的处理逻辑是比较当前节点，选择最大高度的结果返回。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL)
return 0;
if(root->left==NULL&&root->right==NULL)
return 1;
int left_height = maxDepth(root->left); // 加的1是root节点的高度
int right_height = maxDepth(root->right);
if(left_height > right_height)
return left_height+1;
else
return right_height+1;
}
};
也可以采用前序遍历的方法：
前序遍历是中左右。中的处理逻辑就是把当前的深度+1，而且更新最大深度的值。
class Solution {
public:
int result = 0;
void getdepth(TreeNode* root, int depth)
{
if(root==NULL)
return;
if(depth>result)
result = depth;
depth++;
getdepth(root->left, depth);
depth--;
depth++;
getdepth(root->right, depth);
depth++;
return ;
}
int maxDepth(TreeNode* root) {
//采用前序遍历的方法实现
getdepth(root, 1);
return result;
}
};
111. 二叉树的最小深度
题目链接：
https://leetcode.cn/problems/minimum-depth-of-binary-tree/
算法思想：使用前序遍历。判断的终止条件是左右子树是空，进行判别返回。
代码：
class Solution {
public:
int result=INT_MAX;
void getdepth(TreeNode* root,int depth)
{
if(root==NULL)
return;
if(root->left==NULL&&root->right==NULL)
{
result = result<depth?result:depth;
return;
}
depth++;
getdepth(root->left, depth);
depth--;
depth++;
getdepth(root->right, depth);
depth--;
return;
}
int minDepth(TreeNode* root) {
//求深度，那就是前序遍历
if(root==NULL)
return 0;
getdepth(root,1);
return result;
}
};
222. 完全二叉树的节点个数
题目链接：
https://leetcode.cn/problems/count-complete-tree-nodes/
算法思想：
后续遍历的方法。
递归终止条件是：当以该节点为根节点的树是完全二叉树的时候，直接利用完全二叉树的公式进行计算。
class Solution {
public:
int getcount(TreeNode*root)
{
if(root==NULL)
return 0;
int leftcount = 0;
TreeNode*left = root->left;
while(left)
{
left = left->left;
leftcount++;
cout<<"leftcount:"<<leftcount<<endl;
}
int rightcount = 0;
TreeNode*right = root->right;
while(right)
{
right = right->right;
rightcount++;
}
if(leftcount==rightcount)
return (2<<leftcount)-1;
int lefttotalcount = getcount(root->left);
int righttotalcount = getcount(root->right);
return lefttotalcount+righttotalcount+1;
}
int countNodes(TreeNode* root) {
return getcount(root);
}
};
