leetcode 刷题：二叉树的坡度_leetcode 刷题 二叉树的坡度

二叉树的坡度

题目：

  给定一个二叉树，计算 整个树 的坡度 。
  一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
  整个树 的坡度就是其所有节点的坡度之和。

解题思路

dfs深度遍历+回溯

  首先深度遍历二叉树直到没有子节点为止开始返回，返回左边子节点的和+右边子节点的和+该节点的值，并且计算该层的坡度累积到总的坡度和中。
  C++代码如下：

class Solution {
public:
    int count_slope(TreeNode* root,int left_sum,int right_sum,int& res){
        if(root==nullptr){
            return 0;
        }
        left_sum=count_slope(root->left,left_sum,right_sum,res);
        right_sum=count_slope(root->right,left_sum,right_sum,res);
        res+=abs(left_sum-right_sum);
        return left_sum+right_sum+root->val;
    }
    int findTilt(TreeNode* root) {
          //回溯
          int res=0;
          int left_sum=0;
          int right_sum=0;
          count_slope(root,left_sum,right_sum,res);
          return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20