巧解压缩遍历次数求二叉树坡度

原题链接：LeetCode 563. 二叉树的坡度

前言：这是扶明发布的第二篇题解
欢迎小伙伴们评论区就坐 ٩(๑òωó๑)۶

读题

这是一个简单题，题目大意就是：求出所有节点的左右节点的值的差值，需要注意的三个点：

差值的对象是左右子树的节点值的和
差值是绝对值的
可以是空树

解题思路

第一步：将树分解为最小操作单位

很显然就是单个节点

如果对树分解为最小操作单位还不是很熟悉的可以参考一下这篇题解将普通二叉树转换为完全右倾树

第二步：确定题解思路

大家的解法一般是使用一个新的函数返回左右子树的节点值的和，

但这里我们其实可以借助原来的树的节点值直接存储其下子树的节点值之和，

不幸地是这会破坏原来节点的数据所以就姑且就称为过河拆桥法吧(๑•̀ㅂ•́)و✧

第三步：确定遍历顺序

解题步骤已经确定了，就是先要求出左右子树的节点的总和才能求出两边的差值，然而求出节点值的总和需要先遍历子树，故应该是遍历后求值这符合后序遍历的条件，

故选择后序遍历法：（1）先遍历子树以将节点值进行叠加处理二叉树节点的值，（2）求出左右节点的差值返回答案

代码：

class Solution {
public:
    int findTilt(TreeNode* root) {
        if(!root || !root->left && !root->right) return 0;
        int ans = 0, left = 0, right = 0;
        if(root->left){
            ans += findTilt(root->left);
            root->val += root->left->val;
            left = root->left->val;
        } 
        if(root->right){
            ans += findTilt(root->right);
            root->val += root->right->val;
            right = root->right->val;
        } 
        ans += abs(left-right);
        return ans;
    }
};