Leetcode

Binary Tree Tilt

  • Time:O(n)
  • Space:O(\log n)

C++

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;
  }
};

JAVA

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;
  }
}

Python

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