Leetcode Problem 563. Binary Tree Tilt

563. Binary Tree Tilt

Leetcode Solutions

Post-Order Depth-First Search (DFS) to Calculate Tilt

  1. Define a recursive function calculateTiltAndSum(node) that returns a tuple containing the tilt of the current node and the sum of values in the subtree rooted at the current node.
  2. If the current node is null, return (0, 0) as the tilt and sum.
  3. Recursively call calculateTiltAndSum(node.left) to get the left tilt and left sum.
  4. Recursively call calculateTiltAndSum(node.right) to get the right tilt and right sum.
  5. Calculate the current node's tilt as the absolute difference between the left sum and the right sum.
  6. Calculate the sum of the current subtree as the sum of the current node's value, the left sum, and the right sum.
  7. Add the current node's tilt to the total tilt.
  8. Return the current node's tilt and the sum of the current subtree.
  9. Call calculateTiltAndSum(root) and return the total tilt.
UML Thumbnail

Iterative In-Order Traversal with Tilt Calculation

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...