leetcode每日一题-563:二叉树的坡度

链接

二叉树的坡度

题目

分析

简单的dfs问题。首先明确思路，我们需要遍历每一个点，然后求出该点左右子树的值的总和，然后做差，答案累计这个差值即可。那么问题就转化到求每个节点左右子树值的综合上面，同样是一个dfs问题，但是这个问题有一个优化，我们在之后的代码部分进行详细的分析。

代码

C++

/**
 * 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 res = 0;
    int findTilt(TreeNode* root) {
        // 首先对节点判空,如果是空,那么结果为0,直接返回即可.
        if(root == nullptr) return res;
        // 遍历整个树
        dfs(root);
        // 返回结果值
        return res;
    }

    void dfs(TreeNode* root)
    {
        // 分别记录左右子树值的总和,初始值为0
        int l = 0, r = 0;
        // 如果存在左子树就更新左子树值的总和
        if(root->left) l = sum(root->left);
        // 如果存在右子树就更新右子树值的总和
        if(root->right) r = sum(root->right);
        // 答案记录一下差值
        res += abs(l - r);
        // 如果存在左节点就计算左节点的坡度
        if(root->left) dfs(root->left);
        // 如果存在右节点就计算右节点的坡度
        if(root->right) dfs(root->right);
    }

    int sum(TreeNode* root) 
    {
        // 计算当前节点值的总和
        // 左子树的值
        int l = 0;
        // 右子树的值
        int r = 0;
        // 如果存在左子树就更新左子树的值(递归更新)
        if(root->left) l = sum(root->left);
        // 如果存在右子树就更新右子树的值(递归更新)
        if(root->right) r = sum(root->right);
        // 返回当前节点值的总和
        return root->val + l + r;
    }
};

C++

优化

我们经过简单的思考就可以发现，解法一实在是太繁琐了，我们每遍历一个点，就需要查询以当前结点为跟的整个树，其中存在大量的重复，那么是否可以优化这个过程呢？我们仔细观察，其实在计算差值的时候，我们也是遍历了整个树，那么我们可以可以边更新边遍历，我们先计算底层的值，然后用底层的值来更新更高一层的值，显然是可以的。

/**
 * 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 {

    int res = 0;

public:
    int findTilt(TreeNode* root) {
       	// 如果根节点非空就递归遍历树
        if(root) dfs(root);
        // 返回结果
        return res;
    }

    // 边计算差值边求当前节点的总和,从底层开始向上遍历
    int dfs(TreeNode* root)
    {
        // 如果是叶子,就返回当前值
        if(!root->left and !root->right) return root->val;

        // 计算当前当前节点的左右子树总和,默认值为0
        int l = 0, r = 0;
        // 如果存在左子树就更新l,此时,先去计算底层的值,向下递归
        if(root->left) l = dfs(root->left);
        // 如果存在右子树就更新r,此时,先去计算底层的值,向下递归
        if(root->right) r = dfs(root->right);
        // 记录下差值
        res += abs(l - r);
        // 返回当前节点的值的总和
        return l + r + root->val;
    }
};

Java

class Solution {
    int ans = 0;

    public int findTilt(TreeNode root) {
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int sumLeft = dfs(node.left);
        int sumRight = dfs(node.right);
        ans += Math.abs(sumLeft - sumRight);
        return sumLeft + sumRight + node.val;
    }
}

作者：LeetCode-Solution