LeetCode 563简单树 · BST

二叉树的坡度图解题解

这道题到底在问什么

给定二叉树 root。节点坡度 = |左子树节点和 - 右子树节点和|，没有的那一边按 0 算，空节点坡度为 0。返回所有节点坡度之和。节点值范围 -1000 ≤ Node.val ≤ 1000。

输入: root=[1,2,3]
输出: 1（节点 1 坡度 |2-3|=1，两个叶子都是 0）

最优解：一步一步想明白

3记住这条主线：DFS 返回的是「子树和」，坡度是顺路在每个节点结算时累加的副产品。
4栈空，累计坡度 0开局累计坡度是 0。后序 DFS 从根 50 出发，但根的坡度现在算不了，得先知道左右子树各自的和。所以先一路往左下钻，钻到最左下的叶子，再自底向上一个个结算。盯住右边的坡度结算面板，每结算一个内部节点，累计坡度就涨一截。
5进入 50递归进入节点 50（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
6进入 20递归进入节点 20（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
7进入 30递归进入节点 30（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
8叶子 80递归走到节点 80（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
9子树和 = 80结算叶子 80：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 80。节点变绿表示处理完。
10叶子 10递归走到节点 10（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
11子树和 = 10结算叶子 10：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 10。节点变绿表示处理完。
12坡度 = |80-10| = 70节点 30 的左右子树和都齐了：左边 80，右边 10。本节点坡度 = |80-10| = 70，累加进总答案，累计坡度涨到 70。它往上交的子树和 = 30+80+10 = 120。节点变绿。
13叶子 90递归走到节点 90（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
14子树和 = 90结算叶子 90：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 90。节点变绿表示处理完。
15坡度 = |120-90| = 30节点 20 的左右子树和都齐了：左边 120，右边 90。本节点坡度 = |120-90| = 30，累加进总答案，累计坡度涨到 100。它往上交的子树和 = 20+120+90 = 230。节点变绿。
16进入 70递归进入节点 70（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
17叶子 60递归走到节点 60（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
18子树和 = 60结算叶子 60：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 60。节点变绿表示处理完。
19叶子 40递归走到节点 40（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
20子树和 = 40结算叶子 40：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 40。节点变绿表示处理完。
21坡度 = |60-40| = 20节点 70 的左右子树和都齐了：左边 60，右边 40。本节点坡度 = |60-40| = 20，累加进总答案，累计坡度涨到 120。它往上交的子树和 = 70+60+40 = 170。节点变绿。
22坡度 = |230-170| = 60节点 50 的左右子树和都齐了：左边 230，右边 170。本节点坡度 = |230-170| = 60，累加进总答案，累计坡度涨到 180。它往上交的子树和 = 50+230+170 = 450。节点变绿。
2370 + 30 + 20 + 60九个节点全部结算完。看右边的坡度面板：五个叶子坡度都是 0，对总和没贡献；真正出力的是四个内部节点，坡度分别是节点 30 的 70、节点 20 的 30、节点 70 的 20、根 50 的 60。把它们相加就是最终答案。
24答案 = 18070 加 30 加 20 加 60，正好等于 180，这就是整棵树的坡度。回头看，整个过程只走了一遍后序遍历，子树和一路往上递，坡度顺路累加，一次搞定，时间是 O(n)。

⚠️ 容易写错的地方

✗ 错：让 dfs 返回坡度

✓ 对：dfs 必须返回「子树和」，坡度用全局变量累加

父节点要的是孩子的子树和，不是孩子的坡度，返回错东西全盘崩

✗ 错：用前序去算

✓ 对：必须后序：先有左右子树和才能算父亲

父节点的和与坡度都依赖孩子，孩子没算完父亲就是错的

✗ 错：坡度忘了取绝对值

✓ 对：坡度 = |左 - 右|

题目明确是差的绝对值，漏了绝对值负数会把总和算小

完整代码（Python / C++ / Java）

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

复杂度

时间

O(n)

后序遍历每个节点只被访问、结算一次，算和与算坡度都是常数操作

空间

O(h)

只用递归栈，深度等于树高 h；最坏（链状树）退化到 O(n)，平衡树则是 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着二叉树的坡度的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么不能一遍前序就把坡度都算出来？+

因为一个节点的坡度依赖它左右子树的和，而子树和又依赖更深的节点，必须先把孩子全部算完才能算父亲。这正是后序「左、右、根」的顺序。前序是先碰父亲，那时孩子还没算，根本拿不到左右子树和。

如果树非常深，递归会爆栈吗？怎么改？+

链状树深度可达 n，递归栈会很深。可以改成显式栈的迭代后序遍历，或者用带父指针、记录每个节点已算子树和的方式自底向上结算。面试时能说清「后序本质是先子后父」并给出迭代替代方案就够了。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把二叉树的坡度一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 563简单树 · BST

二叉树的坡度图解题解

这道题到底在问什么

输入: root=[1,2,3]
输出: 1（节点 1 坡度 |2-3|=1，两个叶子都是 0）

最优解：一步一步想明白

3记住这条主线：DFS 返回的是「子树和」，坡度是顺路在每个节点结算时累加的副产品。
4栈空，累计坡度 0开局累计坡度是 0。后序 DFS 从根 50 出发，但根的坡度现在算不了，得先知道左右子树各自的和。所以先一路往左下钻，钻到最左下的叶子，再自底向上一个个结算。盯住右边的坡度结算面板，每结算一个内部节点，累计坡度就涨一截。
5进入 50递归进入节点 50（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
6进入 20递归进入节点 20（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
7进入 30递归进入节点 30（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
8叶子 80递归走到节点 80（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
9子树和 = 80结算叶子 80：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 80。节点变绿表示处理完。
10叶子 10递归走到节点 10（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
11子树和 = 10结算叶子 10：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 10。节点变绿表示处理完。
12坡度 = |80-10| = 70节点 30 的左右子树和都齐了：左边 80，右边 10。本节点坡度 = |80-10| = 70，累加进总答案，累计坡度涨到 70。它往上交的子树和 = 30+80+10 = 120。节点变绿。
13叶子 90递归走到节点 90（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
14子树和 = 90结算叶子 90：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 90。节点变绿表示处理完。
15坡度 = |120-90| = 30节点 20 的左右子树和都齐了：左边 120，右边 90。本节点坡度 = |120-90| = 30，累加进总答案，累计坡度涨到 100。它往上交的子树和 = 20+120+90 = 230。节点变绿。
16进入 70递归进入节点 70（紫色）。它还有孩子，左右子树和都不知道，坡度先算不了，所以继续往下钻，先把左孩子那一支彻底搞定。
17叶子 60递归走到节点 60（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
18子树和 = 60结算叶子 60：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 60。节点变绿表示处理完。
19叶子 40递归走到节点 40（紫色），它没有孩子，是叶子。叶子左右两边都是空，子树和都按 0 算，下一帧直接结算。
20子树和 = 40结算叶子 40：左右都是空，坡度 = |0-0| = 0，对总答案没有贡献。它要往上交的「子树和」就是它自己 40。节点变绿表示处理完。
21坡度 = |60-40| = 20节点 70 的左右子树和都齐了：左边 60，右边 40。本节点坡度 = |60-40| = 20，累加进总答案，累计坡度涨到 120。它往上交的子树和 = 70+60+40 = 170。节点变绿。
22坡度 = |230-170| = 60节点 50 的左右子树和都齐了：左边 230，右边 170。本节点坡度 = |230-170| = 60，累加进总答案，累计坡度涨到 180。它往上交的子树和 = 50+230+170 = 450。节点变绿。
2370 + 30 + 20 + 60九个节点全部结算完。看右边的坡度面板：五个叶子坡度都是 0，对总和没贡献；真正出力的是四个内部节点，坡度分别是节点 30 的 70、节点 20 的 30、节点 70 的 20、根 50 的 60。把它们相加就是最终答案。
24答案 = 18070 加 30 加 20 加 60，正好等于 180，这就是整棵树的坡度。回头看，整个过程只走了一遍后序遍历，子树和一路往上递，坡度顺路累加，一次搞定，时间是 O(n)。

⚠️ 容易写错的地方

✗ 错：让 dfs 返回坡度

✓ 对：dfs 必须返回「子树和」，坡度用全局变量累加

父节点要的是孩子的子树和，不是孩子的坡度，返回错东西全盘崩

✗ 错：用前序去算

✓ 对：必须后序：先有左右子树和才能算父亲

父节点的和与坡度都依赖孩子，孩子没算完父亲就是错的

✗ 错：坡度忘了取绝对值

✓ 对：坡度 = |左 - 右|

题目明确是差的绝对值，漏了绝对值负数会把总和算小

完整代码（Python / C++ / Java）

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

复杂度

时间

O(n)

后序遍历每个节点只被访问、结算一次，算和与算坡度都是常数操作

空间

O(h)

只用递归栈，深度等于树高 h；最坏（链状树）退化到 O(n)，平衡树则是 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着二叉树的坡度的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么不能一遍前序就把坡度都算出来？+

如果树非常深，递归会爆栈吗？怎么改？+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

二叉树的坡度 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

二叉树的坡度 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

二叉树的坡度图解题解

二叉树的坡度图解题解