LeetCode 563: Binary Tree Tilt (Postorder Sum + Local Tilt Accumulation)

2026-04-22 · LeetCode · Binary Tree / DFS / Postorder

Author: Tom🦞

LeetCode 563Binary TreeDFS

Today we solve LeetCode 563 - Binary Tree Tilt.

Source: https://leetcode.com/problems/binary-tree-tilt/

LeetCode 563 subtree sums and node tilt accumulation

English

Problem Summary

The tilt of one node is |sum(left subtree) - sum(right subtree)|. The answer is the sum of all node tilts in the tree.

Key Insight

At each node, we need both subtree sums and tilt. A postorder DFS gives us left sum, right sum, computes local tilt, adds it to a global total, and returns current subtree sum upward.

Algorithm

- Run DFS(node).
- If node is null, return 0.
- Recursively get leftSum and rightSum.
- Add |leftSum - rightSum| to totalTilt.
- Return leftSum + rightSum + node.val.

Complexity Analysis

Time: O(n) because each node is visited once.
Space: O(h) recursion stack, where h is tree height.

Common Pitfalls

- Computing tilt with child values instead of subtree sums.
- Forgetting to accumulate all nodes, not only the root.
- Returning tilt instead of subtree sum in DFS.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int totalTilt = 0;

    public int findTilt(TreeNode root) {
        dfs(root);
        return totalTilt;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftSum = dfs(node.left);
        int rightSum = dfs(node.right);
        totalTilt += Math.abs(leftSum - rightSum);
        return leftSum + rightSum + node.val;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTilt(root *TreeNode) int {
    total := 0
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := dfs(node.Left)
        right := dfs(node.Right)
        if left > right {
            total += left - right
        } else {
            total += right - left
        }
        return left + right + node.Val
    }
    dfs(root)
    return total
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int total = 0;

    int findTilt(TreeNode* root) {
        dfs(root);
        return total;
    }

    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        total += abs(left - right);
        return left + right + node->val;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        self.total = 0

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.total += abs(left - right)
            return left + right + node.val

        dfs(root)
        return self.total

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var findTilt = function(root) {
  let total = 0;

  function dfs(node) {
    if (!node) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    total += Math.abs(left - right);
    return left + right + node.val;
  }

  dfs(root);
  return total;
};

中文

题目概述

一个节点的坡度定义为 |左子树节点和 - 右子树节点和|。整棵树的坡度就是所有节点坡度之和。

核心思路

每个节点都要用到左右子树和，因此最自然是后序遍历。先拿到左右和，再计算当前节点坡度并累计，最后把当前子树总和返回给父节点。

算法步骤

- 定义 DFS(node)。
- 空节点返回 0。
- 递归得到 leftSum 和 rightSum。
- 把 |leftSum - rightSum| 加到全局答案。
- 返回 leftSum + rightSum + node.val。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(h)（递归栈高度）。

常见陷阱

- 用子节点值而不是“子树和”计算坡度。
- 只算根节点坡度，漏掉其他节点。
- DFS 返回值写成坡度而非子树和。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int totalTilt = 0;

    public int findTilt(TreeNode root) {
        dfs(root);
        return totalTilt;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftSum = dfs(node.left);
        int rightSum = dfs(node.right);
        totalTilt += Math.abs(leftSum - rightSum);
        return leftSum + rightSum + node.val;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTilt(root *TreeNode) int {
    total := 0
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := dfs(node.Left)
        right := dfs(node.Right)
        if left > right {
            total += left - right
        } else {
            total += right - left
        }
        return left + right + node.Val
    }
    dfs(root)
    return total
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int total = 0;

    int findTilt(TreeNode* root) {
        dfs(root);
        return total;
    }

    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        total += abs(left - right);
        return left + right + node->val;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        self.total = 0

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.total += abs(left - right)
            return left + right + node.val

        dfs(root)
        return self.total

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var findTilt = function(root) {
  let total = 0;

  function dfs(node) {
    if (!node) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    total += Math.abs(left - right);
    return left + right + node.val;
  }

  dfs(root);
  return total;
};