二叉树的最小、最大深度以及平衡二叉树
程序员文章站
2022-07-14 18:07:57
...
**111. Minimum Depth of Binary Tree **
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
代码如下:
class Solution {
public:
int minDepth(TreeNode* root) {
if(root==NULL)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(root->left==NULL&&root->right==NULL)
return 1;
if(root->left==NULL)
left = INT_MAX;
if(root->right==NULL)
right = INT_MAX;
return left<right ? left + 1 : right + 1;
}
};
**104. Maximum Depth of Binary Tree **
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL)
return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left>right ? left+1:right+1;
}
};
**110. Balanced Binary Tree **
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
代码如下:
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root==NULL)
return true;
int mLeft = maxDepth(root->left);
int mRight = maxDepth(root->right);
if(abs(mLeft-mRight)>1)
return false;
else
return isBalanced(root->left)&&isBalanced(root->right);
}
int maxDepth(TreeNode* node)
{
if(node==NULL)
return 0;
int left = maxDepth(node->left);
int right = maxDepth(node->right);
return left>right? left+1:right+1;
}
};
下一篇: 【Android】spinner下拉框