给定一个二叉树?root?，返回其最大深度。
二叉树的?最大深度?是指从根节点到最远叶子节点的最长路径上的节点数。
在这个函数中：
首先检查当前节点是否为
nullptr。如果是，意味着到达了叶子节点的下一个节点，返回深度0。递归地计算左子树和右子树的深度。
将左子树和右子树深度的最大值加1（当前节点的深度）后返回。
/*
* @lc app=leetcode.cn id=104 lang=cpp
*
* [104] 二叉树的最大深度
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
};
// @lc code=end
在这个函数中：
首先检查当前节点是否为
nullptr。如果是，则返回0。然后检查当前节点是否为叶子节点（没有子节点）。如果是，返回1。
如果当前节点只有左子树或只有右子树，则返回单侧子树的最小深度加1。
如果当前节点有两个子节点，则返回左右子树中的最小深度加1。
/*
* @lc app=leetcode.cn id=111 lang=cpp
*
* [111] 二叉树的最小深度
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
if (root->left == nullptr) {
return minDepth(root->right) + 1;
}
if (root->right == nullptr) {
return minDepth(root->left) + 1;
}
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
};
// @lc code=end
给你一棵?完全二叉树?的根节点?root?，求出该树的节点个数。
完全二叉树?的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第?h?层，则该层包含?1~?2h?个节点。
在这个函数中：
首先检查根节点是否为
nullptr。如果是，则返回0。计算左子树和右子树的高度。
如果左右子树的高度相同，则根据满二叉树的性质计算节点总数。
如果左右子树的高度不同，则递归地计算左右子树的节点数，并将它们加上根节点本身。
/*
* @lc app=leetcode.cn id=222 lang=cpp
*
* [222] 完全二叉树的节点个数
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = 0, rightHeight = 0;
TreeNode *left = root, *right = root;
while (left != nullptr) {
leftHeight++;
left = left->left;
}
while (right != nullptr) {
rightHeight++;
right = right->right;
}
if (leftHeight == rightHeight) {
return (1 << leftHeight) - 1;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
// @lc code=end