[系列文章] leetcode每日一题563

发布于 26 天前  124 次阅读


leetcode 563 Binary Tree Tilt

Description

Given the root of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if there the node does not have a right child.

Solution

此题很显然是基于一个递归的思想,对于每个节点,计算其左右子树的和值之差,更新该节点的值,累加到ans中即可,返回左右子树和值以及当前节点的和至上一级调用。

Code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func findTilt(root *TreeNode) (ans int) {
    helper(root, &ans)
    return
}

func absDiff(a, b int) int {
    num := a - b
    if num > 0 {
        return num
    }
    return -num
}

func helper(root *TreeNode, ans *int) int {
    if root == nil {
        return 0
    }
    left, right := helper(root.Left, ans), helper(root.Right, ans)
    *ans += absDiff(left, right)
    return left + right + root.Val
}

一只在互联网躬耕的菜鸟,写代码是热爱,二次元也是,mikoto也是