2022/07/30

Leetcode Note: Go - Binary Tree Tilt

Binary Tree Tilt - LeetCode
https://leetcode.com/problems/binary-tree-tilt/

  • Go 言語で取り組んだメモ

所感

  • binary tree の計算
  • 左右のサブツリーノードの合計値を使って絶対値の差を計算して int で return していく
  • 左右のサブツリーノードが、それぞれ左右の子ノードを持たない場合は合計を 0 として計算する

回答

Binary Tree Tilt - LeetCode
https://leetcode.com/problems/binary-tree-tilt/solution/

Go: bottom up solution - LeetCode Discuss
https://leetcode.com/problems/binary-tree-tilt/discuss/572560/Go%3A-bottom-up-solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTilt(root *TreeNode) int {
    _, res := tilt(root)
    return res
}

func tilt(root *TreeNode) (int,int) {
    if root == nil {
        return 0, 0
    }
    left, s1 := tilt(root.Left)
    right, s2 := tilt(root.Right)
    return (root.Val+left+right), (abs(left-right)+s1+s2)
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
  • 再帰関数を実装して Node を操作していきつつ、差を値を計算して return する

See Also