leetcode 563. 二叉树的坡度（Java版）

ゝ一纸荒年。 2022-10-16 01:58 90阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/binary-tree-tilt/][https_leetcode-cn.com_problems_binary-tree-tilt]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

从问题的描述中，可以清楚地了解到，我们需要在给定树的每个结点处找到其坡度，并将所有的坡度相加以获得最终结果。要找出任意结点的坡度，我们需要求出该结点的左子树上所有结点和以及其右子树上全部结点和的差值。

因此，为了找出解决方案，我们使用递归函数 process，在任何结点调用该函数，都会返回当前结点下面（包括其自身）的结点和。借助于任何结点的左右子结点的这一和值，我们可以直接获得该结点所对应的坡度。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
    class Solution { 
        int sum = 0;
    
        public int findTilt(TreeNode root) { 
            process(root);
            return sum;
        }
    
        public int process(TreeNode node) { 
            if (node == null) return 0;
            int l = process(node.left);
            int r = process(node.right);
            sum += Math.abs(l - r); // 不能既作为返回值又相加，所以独立用sum存储
            return l + r + node.val; // 当前节点的节点和
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_binary-tree-tilt]: https://leetcode-cn.com/problems/binary-tree-tilt/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221014/3563edcd3157471dbe003ed4cefa9982.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221014/de25bad5671345c6abb026c93c45d194.png