二叉树的坡度 图解题解

节点坡度和全树坡度，到底在算什么

给一棵二叉树 root。一个节点的坡度，是它左子树所有节点之和、减去右子树所有节点之和，再取绝对值；哪边没有孩子，那边的和按 0 算，空节点坡度是 0。整棵树的坡度，是把每个节点的坡度全加起来。题面例子 root=[1,2,3]，根 1、两个孩子 2 和 3 都是叶子：叶子没有子树，坡度都是 0；根的左子树只有 2、和为 2，右子树只有 3、和为 3，坡度 |2-3|=1。三个相加，答案就是 1。

对着每个节点分别求两次子树和，慢在哪

照着定义直接做：遍历每个节点，站在它这里把左子树求一遍和、右子树求一遍和，相减取绝对值。麻烦在于『求某棵子树的和』就得把那棵子树整个走一遍，每个节点都来一次，越靠上的节点被反复累加、重复得越狠。n 个节点最坏要 O(n²)，同一批数白白加了许多遍。

一趟后序遍历，怎么把子树和一路带上来

重复求和之所以发生，是因为父节点要的『左右子树和』在处理孩子时就能得到，不必回头重算。把顺序倒过来：先把左右孩子处理完、拿到各自的子树和，再处理当前节点——这正是后序遍历，孩子先把子树和交上来，父节点才开始结算。一个节点的子树和，等于自己的值加左子树和、再加右子树和；孩子把子树和交上来，父节点一个加法就得到。

递归返回子树和，坡度另存一个全局答案累加

写一个 dfs：走到空节点返回 0。否则先递归左孩子拿到左子树和 l、再递归右孩子拿到右子树和 r。此刻两个子树和都齐了，本节点坡度就是 l 和 r 之差的绝对值 abs(l-r)，加进全局答案 ans；然后 dfs 返回本节点的子树和 l+r+根值，交给上一层的父节点。

这里的分工要拎清：dfs 向上返回的必须是子树和，不是坡度。父节点算自己的和与坡度，都只认孩子的子树和，用不到孩子的坡度；坡度是每个节点结算后直接累进 ans 的副产品，从不往上传。dfs 若返回坡度，父节点收到的数全错，整棵树跟着崩。

root=[1,2,3] 后序走一遍，ans 怎么变成 1

这棵树三个节点：根 1，左孩子 2，右孩子 3，两个孩子都是叶子。后序先走到最左的叶子 2：左右都是空，l=0、r=0，坡度 |0-0|=0，ans 还是 0，往上交的子树和 0+0+2=2。再处理右孩子叶子 3：同样左右为空，坡度 |0-0|=0，ans 仍是 0，子树和 0+0+3=3。

两个孩子都结算完，轮到根 1：左子树和 l=2、右子树和 r=3 都到手，坡度 |2-3|=1，加进 ans，ans 从 0 变成 1；根往上交的子树和 2+3+1=6，但根没有父亲，6 用不上。全树走完，ans=1，就是答案。

返回错了东西，整棵树的答案跟着废

复杂度上：全树只做一遍后序遍历，每个节点结算一次，求和与算坡度都是常数操作，时间 O(n)；额外空间只有递归栈，深度等于树高 h，平衡树 O(log n)，链状树最坏 O(n)。

dfs 返回坡度而不是子树和，父节点拿到的数从源头就错；改用前序、孩子没算完就结算父亲，左右子树和根本没到手；坡度忘了取绝对值，左小右大算出负数，把总和拉小。边界反倒省心：空树和单节点树坡度都是 0，没有孩子可比。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# 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:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            nonlocal ans
            ans += abs(l - r)
            return l + r + root.val

        ans = 0
        dfs(root)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * 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 findTilt(TreeNode* root) {
        int ans = 0;
        function<int(TreeNode*)> dfs = [&]( TreeNode* root ) -> int {
            if (!root) {
                return 0;
            }
            int l = dfs(root->left), r = dfs(root->right);
            ans += abs(l - r);
            return l + r + root->val;
        };
        dfs(root);
        return ans;
    }
};

Java

import java.util.*;
/**
 * 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 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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int ans;

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

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = dfs(root.left), r = dfs(root.right);
        ans += Math.abs(l - r);
        return l + r + root.val;
    }
}