Skip to content

563. Binary Tree Tilt 👎

  • Time: $O(n)$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int findTilt(TreeNode* root) {
    int ans = 0;
    sum(root, ans);
    return ans;
  }

 private:
  int sum(TreeNode* root, int& ans) {
    if (!root)
      return 0;

    const int l = sum(root->left, ans);
    const int r = sum(root->right, ans);
    ans += abs(l - r);
    return root->val + l + r;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int findTilt(TreeNode root) {
    sum(root);
    return ans;
  }

  private int ans = 0;

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

    final int l = sum(root.left);
    final int r = sum(root.right);
    ans += Math.abs(l - r);
    return root.val + l + r;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def findTilt(self, root: Optional[TreeNode]) -> int:
    ans = 0

    def summ(root: Optional[TreeNode]) -> None:
      nonlocal ans
      if not root:
        return 0

      l = summ(root.left)
      r = summ(root.right)
      ans += abs(l - r)
      return root.val + l + r

    summ(root)
    return ans