详情

    深度优先遍历，时间复杂度 O(n) 空间复杂度 O(n)

    1. /**
    2.  * Definition for a binary tree node.
    3.  * type TreeNode struct {
    4.  *     Val int
    5.  *     Left *TreeNode
    6.  *     Right *TreeNode
    7.  * }
    8.  */
    9. func findTilt(root *TreeNode) (ans int) {
    10.     var dfs func(*TreeNode) int
    11.     dfs = func(node *TreeNode) int {
    12.         if node == nil {
    13.             return 0
    14.         }
    15.         sumLeft := dfs(node.Left)
    16.         sumRight := dfs(node.Right)
    17.         ans += abs(sumLeft - sumRight)
    18.         return sumLeft + sumRight + node.Val
    19.     }
    20.     dfs(root)
    21.     return
    22. }
    24. func abs(x int) int {
    25.     if x < 0 {
    26.         return -x
    27.     }
    28.     return x
    29. }