563. 二叉树的坡度
二叉树大部分题目都可以用递归解决。为了满足一般性，即使题目初试没有的情况，子问题有的，也要考虑。
递归就考虑当前的情况就行了，不要再考虑上一层或者下一层。
下面这个做法是把计算值和、计算坡度分开，时间复杂度n^2，一开始做的时候就一直在想n的情况，就没有写出来。
class Solution { public: int sum(TreeNode* root) { if(root==nullptr) return 0; return root->val+sum(root->left)+sum(root->right); } int findTilt(TreeNode* root) { if(root==nullptr) return 0; return abs(sum(root->left)-sum(root->right))+findTilt(root->left)+findTilt(root->right); } };
下面是时间效率最高的解法：
class Solution { public: int res=0; int dfs(TreeNode* root) { if(root==nullptr) return 0; int left=dfs(root->left); int right=dfs(root->right); res+=abs(left-right); return root->val+left+right; } int findTilt(TreeNode* root) { dfs(root); return res; } };
