104. 二叉树的最大深度
题目：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
解法1：递归
class Solution {
public:
int maxDepth(TreeNode* root) {
if (NULL == root)
return 0;
int leftDep = maxDepth(root->left) + 1;
int rightDep = maxDepth(root->right) + 1;
return leftDep > rightDep ? leftDep : rightDep;
}
};
在递归中，如果不想用到临时变量，可以选择用max()方法。具体程序可参考如下：
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) {
return 0;
}
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
有时候调用max()方法，程序无法识别，就会想到宏，具体程序可参考如下：
#define MAX(x,y) ((x)>(y)?(x):(y)) //莫忘最外层括号
class Solution {
public:
int maxDepth(TreeNode* root) {
if (NULL == root)
return 0;
return MAX(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
但是，这种实现会超出时间限制。为什么呢？
不由得想说明是宏？是在预编译的时候进行文本替换，那么在MAX的地方，运行时会调用maxDepth()三次：((x)>(y)?(x):(y))。所以当树比较深的时候会超时。因此，宏不要用在递归函数上。
解法2：用从上到下打印二叉树的思想，深度即层数
class Solution {
public:
int maxDepth(TreeNode* root) {
if(nullptr == root)
return 0;
queue<TreeNode*> que;
que.push(root);
int depth = 0;
while(!que.empty()){
depth++;
int len =que.size();
while (len--) {
TreeNode* node=que.front();
que.pop();
if(node->left!=nullptr)
que.push(node->left);
if(node->right!=nullptr)
que.push(node->right);
}
}
return depth;
}
};
解法3：用一个全局变量记录层数，每层判断
class Solution {
public:
void cntLevel(TreeNode* root, int curLevel, int& depth) {
if (NULL == root)
return;
if (curLevel > depth)
depth = curLevel;
cntLevel(root->left, curLevel + 1, depth);
cntLevel(root->right, curLevel + 1, depth);
}
int maxDepth(TreeNode* root) {
int depth = 0;
cntLevel(root, 1, depth);
return depth;
}
};
这种方法，没有递归调用，也不用操作具体的节点，效率较高。
110. 平衡二叉树
题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
解法1：计算数的深度，由上至下
class Solution {
private:
int treeDepth(TreeNode* root) {
if (NULL == root)
return 0;
return max(treeDepth(root->left), treeDepth(root->right)) + 1;
}
public:
bool isBalanced(TreeNode* root) {
if (NULL == root)
return true;
return abs(treeDepth(root->left) - treeDepth(root->right)) <= 1
&& isBalanced(root->left)
&& isBalanced(root->right);
}
};
解法2：由下至上，子树不平衡即不平衡
class Solution {
private:
bool isBalance(TreeNode* root, int& deep) {
if (NULL == root) {
deep = 0;
return true;
}
int leftLen, rightLen;
if (isBalance(root->left, leftLen)
&& isBalance(root->right, rightLen)
&& abs(leftLen - rightLen) <= 1) {
deep = max(leftLen, rightLen) + 1;
return true;
}
return false;
}
public:
bool isBalanced(TreeNode* root) {
if (NULL == root)
return true;
int deep = 0;
return isBalance(root, deep);
}
};
这种思路是在计算长度的时候，及时判断是否为平衡。此思路还有另一种实现，具体如下程序：
class Solution {
private:
int depth(TreeNode* root, bool& flag) {
if (NULL == root) {
flag = true;
return 0;
}
bool left, right;
int leftLen = depth(root->left, left);
int rightLen = depth(root->right, right);
if (left && right && abs(leftLen - rightLen) <= 1) {
flag = true;
return max(leftLen, rightLen) + 1;
}
flag = false;
return -1; //无效，无须计算
}
public:
bool isBalanced(TreeNode* root) {
if (NULL == root)
return true;
bool flag;
depth(root, flag);
return flag;
}
};
111. 二叉树的最小深度
题目：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
题目要点：
最小深度定义为到最近叶子节点的深度，当左右子树都为空，最小深度才为1。
解法1：分类讨论子节点情况
class Solution {
public:
int minDepth(TreeNode* root) {
if (NULL == root)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if (0 == left && 0 == right) //1为根节点所在的深度
return 1;
if (0 == left || 0 == right)
return 0 == left ? right + 1 : left + 1;
return min(left, right) + 1;
}
};
这种解法根据返回情况写的很详细直白，理解后返回判断可以进一步简写如下：
class Solution {
public:
int minDepth(TreeNode* root) {
if (NULL == root)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if (0 == left || 0 == right)
return max(left, right) + 1; //1为根节点所在的深度
return min(left, right) + 1;
}
};
甚至可以直接简写为一个三元式，具体程序如下：
class Solution {
public:
int minDepth(TreeNode* root) {
if (NULL == root)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
return (left && right) ? 1 + min(left, right) : 1 + left + right;
}
};
其中(left && right)不成立时，说明左右子节点至少有一个为空，即left和right至少有一个为0, 1+left+right数值上等于要求的数，没有别的特殊意义。
有很多同学第一次写，很容易写成如下程序（本题的错误解法，通不过的测试例如[1,2]），这就是没有好好理解最小深度的定义。
class Solution {
public:
int minDepth(TreeNode* root) {
if (NULL == root)
return 0;
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
};
解法2：用从上至下打印二叉树的队列思路，遇到叶子节点短路处理
class Solution {
public:
int minDepth(TreeNode* root) {
if(NULL == root)
return 0;
queue<TreeNode*> que;
que.push(root);
int depth = 0;
while(!que.empty()){
int len = que.size();
while (len--) {
TreeNode* node = que.front();
que.pop();
if(NULL == node->left && NULL == node->right)
return depth + 1;
if(node->left)
que.push(node->left);
if(node->right)
que.push(node->right);
}
depth++;
}
return depth;
}
};
这种思路，处理到第一个叶子节点就结束了，效率较好。
