|
写递归解法的时候多会有一个疑惑，就是在原来的答案的函数上去递归，还是写一个新的函数去递归？
这个时候你就要去缕一缕你的递归是怎么出来的，你的功能A是什么？
这道题就是，要判断一个树所有节点的左右子树的高度差和1的关系，然后左右子树的高度哪里来，子树的左右儿子判断完之后加1就得到了子树的高度，然后执行判断。那么就需要一直走到底高度显而易见然后判断高度差，返回到上一层就知道了高度，进而可以计算高度差，进而可以知道是否平衡，当前节点平衡，那就继续往上顶。
所以你现在看，他求高度和判断该节点是否平衡是一块的，所以说这个题目给的答案函数不就是让判断平衡与否么，所以直接在原来的函数上操作就得了！
/**
* 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:
bool isBalanced(TreeNode* root) {
if(root == nullptr)return 1;
if(root->left == nullptr && root->right == nullptr){
return 1;
}
int leftHeight, rightHeight;
leftHeight = isBalanced(root->left);
rightHeight = isBalanced(root->right);
if(leftHeight == -1 || rightHeight == -1) return -1;
if(abs(leftHeight - rightHeight) <= 1){
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
else{
return -1;
}
}
};
这个是第一次提交的，最后泥马的全都会返回-1，-1在bool类型看来是真的。
修改之后，考虑改成0以做区分，
/**
* 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:
bool isBalanced(TreeNode* root) {
if(root == nullptr)return 1;
if(root->left == nullptr && root->right == nullptr){
return 1;
}
int leftHeight, rightHeight;
leftHeight = isBalanced(root->left);
rightHeight = isBalanced(root->right);
if(leftHeight == 0 || rightHeight == 0) return 0;
if(abs(leftHeight - rightHeight) <= 1){
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
else{
return 0;
}
}
};
上边这个依旧是错的，原因是啥呢，就是他妈的isBalanced，这个函数，你虽然在递归的时候返回的是深度，但是他他妈的给你转成了bool类型，也就是变成了0和1.
/**
* 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 isBalanced1(TreeNode* root) {
if(root == nullptr)return 1;
if(root->left == nullptr && root->right == nullptr){
return 1;
}
int leftHeight, rightHeight;
leftHeight = isBalanced1(root->left);
rightHeight = isBalanced1(root->right);
if(leftHeight == 0 || rightHeight == 0) return 0;
if(abs(leftHeight - rightHeight) <= 1){
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
else{
return 0;
}
}
bool isBalanced(TreeNode* root) {
return isBalanced1(root);
}
};
输入：
[1,null,2,null,3]
输出：
true
预期结果：
false
这个依旧是错误的，这个错误的原因是啥呢？就是因为在最开始的时候，我把空节点直接返回了1，本来该返回0的，当时想的是由于往下遍历不可能会递归到空节点的，因为由下面的一行判断，只要当前节点的左右都空了，直接就可以return了，但是这里遗漏了一个点，就是如果根节点只有一个儿子呢，那么你就会把他的空儿子直接放进去了，这时候按照原来的思路，你应该返回的是儿子的高度也就是空也就是0。
/**
* 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 isBalanced1(TreeNode* root) {
if(root == nullptr)return 0;
if(root->left == nullptr && root->right == nullptr){
return 1;
}
int leftHeight, rightHeight;
leftHeight = isBalanced1(root->left);
rightHeight = isBalanced1(root->right);
if(leftHeight == 0 || rightHeight == 0) return 0;
if(abs(leftHeight - rightHeight) <= 1){
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
else{
return 0;
}
}
bool isBalanced(TreeNode* root) {
if(root == nullptr) return 1;
return isBalanced1(root);
}
};
输入：
[1,2]
输出：
false
预期结果：
true
这个又泥马的错了，因为啥呢？
就是当你上边改成了返回0的时候，之前约定的是只有出现了不平衡的情况才返回0，那么你这一整只要是根节点出个空儿子就返回0，那就被认为是不平衡的了。那么这玩意就和上边改动之后一环套一环的错，这时候只需要把原来的不平衡返回0改成返回-1就可以了。
/**
* 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 isBalanced1(TreeNode* root) {
if(root == nullptr)return 0;
if(root->left == nullptr && root->right == nullptr){
return 1;
}
int leftHeight, rightHeight;
leftHeight = isBalanced1(root->left);
rightHeight = isBalanced1(root->right);
if(leftHeight == -1 || rightHeight == -1) return -1;
if(abs(leftHeight - rightHeight) <= 1){
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
else{
return -1;
}
}
bool isBalanced(TreeNode* root) {
if(root == nullptr) return 1;
return isBalanced1(root);
}
};
输入：
[1,2,2,3,3,null,null,4,4]
输出：
true
预期结果：
false
又泥马的错了，为啥呢，又是一环套一环，你把返回值改成了-1，那你的函数最后返回的-1 你的整一下啊，不然-1又被当成真了。
/**
* 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 isBalanced1(TreeNode* root) {
if(root == nullptr)return 0;
if(root->left == nullptr && root->right == nullptr){
return 1;
}
int leftHeight, rightHeight;
leftHeight = isBalanced1(root->left);
rightHeight = isBalanced1(root->right);
if(leftHeight == -1 || rightHeight == -1) return -1;
if(abs(leftHeight - rightHeight) <= 1){
return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}
else{
return -1;
}
}
bool isBalanced(TreeNode* root) {
if(root == nullptr) return 1;
return isBalanced1(root) != -1;
}
};
功夫不负有心人，终于泥马的得了！！！
回到最初的话题，就是对于一个递归你写到他给你的答案的函数里面，还是自己写一个。这里统一规定一下：就是对于自己内心非常明确的，非常有自信且确定的，就直接按照自己想法写就得了。但是只要是不确定的，你他妈的可以在最后写完了这道题，去思考一波然后再尝试尝试，但是一开始做的时候你就直接另外整一个函数去写，因为这样递归就算是可以写在原函数里，现在只是多去写一行调用罢了。所以这里既然另外整一个函数是万能的，那就另外写一个呗！
这道题，虽然最初的时候分析可以写在原函数里，但是泥马的没想到居然还有返回值这一招，所以就最后被迫重新整一个函数。
?另外，多说一点别的东西，就是关于求深度的，以及和他差不多的求高度的：
对于深度，他是从根是深度为起始点，然后往下不断的深度增加，要想算深度需要从上往下算，因为你只有知道了爹有多深，你才能确定你的儿子多深，所以也就是先根后儿子的先序遍历。
对于高度，从最下面的叶节点作为起始点，然后不断往上高度升高，要想算高度就需要从下往上算，因为你只有知道了儿子多高，爹才是高的儿子加1，所以也就是要先儿子后爹的后续遍历。
对于高度和深度之间的一个联系就是：根节点的高度就等于树的最大深度！
那么本题要求的是平衡二叉树平衡问题，也就是高度差问题，也就是求高度的问题。所以说就需要使用后续遍历。
本题如果去写后续递归的话，注意二叉树递归有个特点就是，你访问了当前，然后往两个儿子递归的，回来的时候是你知道了两个儿子的高度之后，再得知当前的新高度，是一个自底向上的过程，针对本题的递归判断节点的平衡与否是先知道儿子的然后再知道爹的。
其实我上边写的递归就是这么一个特点的，父亲的高度是由儿子加1得到的，而儿子出事了不平衡了，爹也就不用判断了。
104.二叉树的最大深度
上边这道题是之前做过的，这里求得时候使用得是后续遍历，
那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这颗树的最大深度，所以才可以使用后序遍历。
这里是做了一个上边得转换得！
如果这道题去写先序得递归得话也不是不能写，也是可以得
class Solution {
public:
int result;
void getDepth(TreeNode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { // 左
depth++; // 深度+1
getDepth(node->left, depth);
depth--; // 回溯，深度-1
}
if (node->right) { // 右
depth++; // 深度+1
getDepth(node->right, depth);
depth--; // 回溯，深度-1
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == NULL) return result;
getDepth(root, 1);
return result;
}
};
可以看出使用了前序（中左右）的遍历顺序，这才是真正求深度的逻辑！
注意以上代码是为了把细节体现出来，简化一下代码如下：
class Solution {
public:
int result;
void getDepth(TreeNode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { // 左
getDepth(node->left, depth + 1);
}
if (node->right) { // 右
getDepth(node->right, depth + 1);
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == 0) return result;
getDepth(root, 1);
return result;
}
};代码随想录得答案
这里有一个至关重要的点要说：就是这个递归是不同于之前的一些递归的，因为你像之前的求树的高度的问题，那不就是拿儿子的高度加1得到的么，那儿子的高度也是可以利用这么一个思路去求的。这是第一种递归，就是递归过程中把每个元素都去求解了这样一个问题，而这些问题是相互嵌套了，也就是大问题变成小问题，小问题解决了就可以解决掉大问题。
所以说最后小问题一直变小就成了可以解决的元问题，也就解决了最开始的大问题，也就是要求的东西。那么这样一个递归，在这个过程中每一个元素都去求了自己的高度。
但是对于本题的先序玩法是不一样的，这个递归根本没有去求每一个节点的最大深度，因为这个深度就是要求的树的最大深度，也就是在所有节点的深度中找最大的，他这个问题之间就没有形成嵌套的一种形式。
所以这里用递归纯粹是实现遍历，整体维护一个最大值，然后不断的遍历，将这个最大值进行更新，最终求出最大的深度！
整体的逻辑就是有个最初的深度，然后每往下一层深度就++，不断的实现遍历，在递归函数中设有一个maxdepth，，不断更新，只需要比较当前深度和maxdepth即可。
另外：上边的第一个代码中写了一些回溯的东西，回去的时候对depth--，因为你从当前函数会到上一级了，也就是从访问儿子回到访问爹了，那么深度肯定减小啊，所以depth就更新了，这是保证一个函数对应的depth是可以对上号的。
但是对于本题而言，这是没有什么作用的，因为啥呢？这道题在你递归到底的时候就已经求出了正确答案了，没必要再在回溯的时候更新回去了，但是这个就是一个重要的点，这里只是没有用上，以后对于回溯问题可就不一定了，所以你要回！
class Solution {
public:
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(TreeNode* root) {
return height(root) >= 0;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1
int getHeight(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right);
if (rightHeight == -1) return -1;
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
上边这俩都是相同思路的答案。
现在回到这道题来，刚刚是用的自底向上的递归，那接下来整一个自顶向下的递归。
class Solution {
public:
int height(TreeNode* root) {
if (root == NULL) {
return 0;
} else {
return max(height(root->left), height(root->right)) + 1;
}
}
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
} else {
return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个递归就没什么水平了，但是仍然有点骚气的，就是他的复杂度比较高，但是实现的过程还是值得研究一下的。
他的思路就是通过递归来实现每个节点的遍历，遍历的同时去求每个节点的左右子树的高度差。骚气的点就是在于他的遍历是通过递归实现的，他的每个节点的左右子树的高度差也是通过递归来求的，所以最后n方的复杂度就是来自两次递归的两个n遍历。
对于迭代的实现：先说一下，深度和高度还有一个去别，就是深度可以用一遍迭代求出来，利用层序遍历就可以，但是高度是做不到的，这里指的是每个节点的深度和高度。那就啥呢，把所有的求高度的转成求深度的。求一个点的高度不就是求该点为根的子树的最大深度么，以此来求每个节点的高度。但是这直接给复杂度来个n，这个也就是n方的复杂度，是和自顶向下的递归是差不多的思路。
class Solution {
private:
int getDepth(TreeNode* cur) {
stack<TreeNode*> st;
if (cur != NULL) st.push(cur);
int depth = 0; // 记录深度
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
if (node != NULL) {
st.pop();
st.push(node); // 中
st.push(NULL);
depth++;
if (node->right) st.push(node->right); // 右
if (node->left) st.push(node->left); // 左
} else {
st.pop();
node = st.top();
st.pop();
depth--;
}
result = result > depth ? result : depth;
}
return result;
}
public:
bool isBalanced(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) return true;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
return false;
}
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
}
return true;
}
};
|