Leetcode563. 二叉树的坡度

题意

求每个节点的左子树的节点之和和右子树节点之和的差的绝对值

思路

  • 其实就是二叉树高度的变种,在二叉树高度的题目里面求的是左右子树的高度,这里求的是子树的节点之和,先看求二叉树高度的代码??
public int maxDepth(TreeNode root) {
    if(root == null) return 0;

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    
    return 1 + Math.max(left, right);
}
  • 要修改的地方是 return 的东西,此时不是要求二叉树的高度,而是要求节点之和,而节点之和显然等于左子树的节点之和 + 右子树节点之和 + 当前节点的值
  • 另外因为要计算所有节点的所以要多一句计算语句

代码(Java)

class Solution {
    private int sumDegree = 0;

    private int calculate(TreeNode root) {
        if(root == null) return 0;

        int left = calculate(root.left);
        int right = calculate(root.right);

        sumDegree += Math.abs(left - right);
        return left + right + root.val;
    }

    public int findTilt(TreeNode root) {
        int allDegree = calculate(root);
        return sumDegree;
    }
}

代码(Python)

class Solution:
    sumDegree = 0
    def findTilt(self, root: TreeNode) -> int:
        def calculate(root):
            if not root: return 0

            left = calculate(root.left)
            right = calculate(root.right)

            self.sumDegree += abs(left - right)
            return left + right + root.val
        calculate(root)
        return self.sumDegree

Leetcode563. 二叉树的坡度

上一篇:计算机网络速率,带宽,吞吐量概念


下一篇:IFS概念