Leetcode563 引起的腥风血雨
昨天总结完二叉树与回溯后，想着顺手刷一道相关的Leetcode巩固一下，却不想随意选的一道题，竟然引起了如此腥风血雨。
满满干货，希望大家坚持读完。
题目
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
思路
昨天搞了一天的二叉树，一看题我就乐了，这不就是几次遍历嘛。
1、给一个节点，遍历求和
2、给一个节点，对左右节点求和，然后求绝对值的差。
3、给一个节点，对所有子节点遍历分别执行2的操作。
结果呢？
先不说结果，我们先把代码贴上来。（丢人啊
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int result = 0;
int findTilt(TreeNode* root) {
if (root) {
this->result += calTilt(root);
findTilt(root->left);
findTilt(root->right);
}
return result;
}
int calTilt(TreeNode* root) {
util l;
int leftSum = l.getSum(root->left);
util r;
int rightSum = r.getSum(root->right);
return abs(leftSum - rightSum);
}
class util{
public:
int sum;
util():sum(0) {};
int getSum(TreeNode* root){
if (root) {
this->sum += root->val;
getSum(root->left);
getSum(root->right);
}
return this->sum;
}
};
};
遇到的问题
思路很简单，但是在实现的时候却遇到了很多的困难：
1、遍历简单，但是求和呢？我第一次先用了下面这样的形式
int getSum(TreeNode* root){
int sum = 0;
if (root) {
sum += root->val;
getSum(root->left);
getSum(root->right);
}
return sum;
}
大家看出其中的毛病了没有？
没错,每次递归都会给sum清零，所以根本实现不了累加。
然后我怎么解决的呢？
给sum加static，然后测试了一下可以了，可是没想到，更大的坑在后面等着我
c++ static
通常，在函数体中定义一个局部变量的值时，编译器在每次函数调用的时候使堆栈的指针向下移动一个合适的位置，为这些局部变量分配内存。如果这个变量有一个初始化表达式，那么每当程序运行到此处，初始化就会被执行。
然而，有时想在两次函数调用之间保留一个变量的值，可以通过定义一个全局变量来实现，但这样一来，这个变量就不仅仅受这个函数的控制，于是，c和c++就有了static，这个对象不保存在堆栈，而是保存在程序的静态数据区，只在函数第一次调用的时候初始化，以后他将在两次函数调用之间保持他的值。
上面这段话摘自《Thinking in C++》
看完这段话，我们对最基础的static 有了最基础的认知，
１、static 的变量不储存在堆栈，而是静态数据区，从而导致他之初始化一次
２、static变量，会在两次调用之间保持相同的值。
也就是这个第二点，让我再一次遇到了坑。
求和函数是写好了，但是呢？
回到前面，我们的第二步是，给一个节点，我们要分别算出他的左右子树的求和，熟悉不？
静态成员，一个函数，两次调用，绝望不？
就这样，我的sum出现了问题，别看现在说的风轻云淡，当时挑错调的都想死了。
（而且，不光这一个问题，先看一段干货）
应该知道，上面的函数很容易出现多线程问题，无论什么时候设计一个包含静态变量的函数时，都应该记住多线程问题。
摘自《Thinking in c++》
那你就纳闷了，话说你也没有用多线程啊？
但是leetcode在检验数据的时候用了啊，我用他给的playground测试同样的代码，结果都不一样，后来上网一查，才发现。
出了问题也没办法，就得想着怎么解决，怎么解决呢？
我想了一下问题出在哪里，就是求和时sum值的传递，既然不能用静态变量，那就当做参数传递进去吧。
于是，
int getSum(TreeNode* root, int sum) {
if (root) {
sum += root->val;
getSum(root->left, sum);
getSum(root->right, sum);
}
return sum;
}
这是我想的第二个办法，但是我也失败了，不知道大家能看出来是哪里吗？
揭晓答案：
sum值在递归过程中没有改变，在回溯到上一个节点的时候，sum值又变成了，上一个节点时的sum值，那么这是为什么呢？
又回到《Thinking in c++》
通常，向函数传递参数时，在函数内部生成一个该参数的拷贝，这称为按值传递.
调用f()时，在函数调用期间为变量a分配临时空间，拷贝x的值给a赋值来初始化它，当f()调用结束时，分配给a的临时空间就消失了
所以，也就是说：
“形式参数不能改变外部对象”。
那么，怎么解决呢？
学过C的，我们知道传递指针就可以解决这个问题，然而，c++提出了一个新的概念，叫做引用传递。
c++ 中的引用和指针其实是一种东西，如果非要说有什么不一样，那么就是引用不会改变函数调用方式，是一种c++中（有的语言也有）的一种语法糖（对于语法的不同调用方式）。
我们看一下怎么用：
int getSum(TreeNode* root, int& sum) {
if (root) {
sum += root->val;
getSum(root->left, sum);
getSum(root->right, sum);
}
return sum;
}
没错，就多了一个符号，就是这么简单。
顺着刚才，继续说。可我当时不知道该加引用啊。所以我是怎么解决的呢？
c++ 的成员内部类：
代码上面贴了，简单说一下，成员内部类成功解决了无法设置静态变量的问题，但是最终用的时间真是不敢恭维。击败百分之17还行？？
刚才实现了一下引用传递的版本，我发现变慢了
static const auto _=[]()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int result = 0;
int initSum = 0;
int findTilt(TreeNode* root) {
if (root) {
this->result += calTilt(root);
findTilt(root->left);
findTilt(root->right);
}
return result;
}
int calTilt(TreeNode* root) {
// util l;
int leftSum = getSum(root->left, initSum);
// util r;
this->initSum = 0;
int rightSum = getSum(root->right, initSum);
this->initSum = 0;
return abs(leftSum - rightSum);
}
int getSum(TreeNode* root, int& sum) {
if (root) {
sum += root->val;
getSum(root->left, sum);
getSum(root->right, sum);
}
return sum;
}
};
递归
在做这道题的时候，我一直在思考层序遍历的过程细节，于是就去看了一下递归有关的东西，然后发现知乎有个回答说的很明白。
所谓“线性递归”，这个“线性”本质上指的是：随着递归的进行，stackframe(栈帧)的增长速率；若这个函数调用，最后所占据的最大stackframe个数为O(n)的话，那么这个递归就被称为“线性递归”，其中n等于递归层数;其实，为什么会这样呢？能否在进行下一层递归之前，将本层递归所使用的stackframe销毁、回收呢？这样不就不用耗费那么深的stackframe了么？这样想当然是好，不过问题就是“办不到”，因为，请注意这一行：return 1 + count_div357(a + 1, b)这一行想要被执行完并且返回，就必须等到这里的这个递归调用返回结果x，然后计算1 + x后返回；也就是说，当前stackframe无法在刚进入下一层递归时销毁，因为这里还有没有完成的计算，它必须等到这里的这个递归调用返回后，拿到结果完成剩下的计算后，才能销毁当前stackframe；所以你可以想象，每一次执行到这一行代码的时候，都新开辟了一个stackframe且本层stackframe没有销毁，那么所有的stackframe势必排成一条长龙，这也就是线性递归的“线性”的来历；
我上面给你解释了一下从调用栈(stackframe)的角度来系统地理解递归；除了你这个题目里面提到的“线性递归”和我在这里扩展的“尾递归”之外，还有一种“树状递归(tree recursion)”，希望你能自己去查查资料，同样通过调用栈的变化的视角，来理解它为何被称为“树状”(其实道理很浅显，我就不多解释了)；至于"为什么要用递归"呢？这个问题，我的理解就是： 我们要解决的很多问题本身的定义就是“递归”的，比如最常见的“树的遍历”，树本身就是一个递归的结构，如果你想要用程序来完成对它的遍历，最自然的方式也就是递归地把这个遍历过程描述出来，试想一下如果你偏要用循环的方式来完成树的遍历得多麻烦？代码长度也会增长很多很多；所以面对递归的问题，递归的解法是最自然的、最好理解的，这就是“为什么用递归”的意义；至于“递归”的设计思路，工程地讲，我认为就是处理好3个点： 1)出口条件,即这个递归什么条件结束？ 2)中间变化过程，即本层递归到下一层递归的“参数变化” 3)初始条件,即递归以什么样的初始条件开始;
这里只摘出我觉的很好的地方，原文在这里
分析最优答案
leetcode里面最优的答案只用了4ms，而且代码量是我的1/2。
先贴代码：
static const auto _=[]()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int findTilt(TreeNode* root) {
int res=0;
treesum(res,root);
return res;
}
int treesum(int & res,TreeNode* root)
{
if(root)
{
int left=treesum(res,root->left);
int right=treesum(res,root->right);
res+=abs(left-right);
return left+right+root->val;
}
else
return 0;
}
};
我们来看一下他的代码，最上面还是熟悉的优化。
然后他的想法是后序遍历，他在一个函数中，用递归算出了最终结果，我认为他的闪光之处就在于他一次遍历完成了我两次遍历做的事情，我一次遍历用来求和，一次遍历求坡度，但是他只用了一次，就全部算出来了。
为了成为传奇，你能承受多大痛苦
