What is the tilt of a node in the Binary Tree Tilt problem?

The tilt of a node is the absolute difference between the sum of the values of its left and right subtrees.

How do I calculate the tilt of a node in a binary tree?

To calculate the tilt, traverse the tree using DFS, calculate the sum of each node’s left and right subtrees, and compute their difference.

What’s the primary traversal method used to solve Binary Tree Tilt?

The solution uses a post-order DFS traversal to calculate the tilt of each node and accumulate the total tilt.

How can GhostInterview help with the Binary Tree Tilt problem?

GhostInterview assists by breaking down the traversal and tilt calculation, and guiding you through common pitfalls.

What is the complexity of solving the Binary Tree Tilt problem?

The time complexity is \mathcal{O}(N) and the space complexity is \mathcal{O}(N), where N is the number of nodes in the tree.

#563

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树的坡度

给你一个二叉树的根节点 root ，计算并返回整个树的坡度。一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的差的绝对值。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。整个树的坡度就是其所有节点的坡度之和。示例 1…

树深度优先搜索二叉树

题目描述

给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度。

一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。

整个树 的坡度就是其所有节点的坡度之和。

示例 1：

输入：root = [1,2,3]
输出：1
解释：
节点 2 的坡度：|0-0| = 0（没有子节点）
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
坡度总和：0 + 0 + 1 = 1

示例 2：

输入：root = [4,2,9,3,5,null,7]
输出：15
解释：
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 5 的坡度：|0-0| = 0（没有子节点）
节点 7 的坡度：|0-0| = 0（没有子节点）
节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）
坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15

示例 3：

输入：root = [21,7,14,1,1,2,2,3,3]
输出：9

提示：

树中节点数目的范围在 [0, 10⁴] 内
-1000 <= Node.val <= 1000

lightbulb

解题思路

方法一：递归

我们设计一个函数 $\text{dfs}$ ，用来计算以当前节点为根节点的子树的节点之和。在 $\text{dfs}$ 函数中，我们首先判断当前节点是否为空，若为空则返回 0。然后递归调用 $\text{dfs}$ 函数计算左子树的节点之和 $l$ 和右子树的节点之和 $r$ 。接着计算当前节点的坡度，即 $|l - r|$ ，并将其加到答案中。最后返回当前节点的节点之和 $l + r + \textit{root.val}$ 。

在主函数中，我们初始化答案为 0，然后调用 $\text{dfs}$ 函数计算整个树的坡度，并返回答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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

speed

复杂度分析

指标	值
时间	\mathcal{O}(N)
空间	\mathcal{O}(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates clear understanding of tree traversal techniques.
question_mark
Candidate can efficiently manage state while performing the DFS.
question_mark
Candidate is able to articulate the trade-offs between different traversal methods.

warning

常见陷阱

外企场景

error
Forgetting to track the sum of each subtree, leading to incorrect tilt calculations.
error
Not properly handling cases where a node has no children, causing incorrect tilt values.
error
Misunderstanding the problem and trying to calculate the tilt with a more complex traversal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Alter the problem to return the tilt of a subtree rather than the entire tree's tilt.
arrow_right_alt
Extend the problem to handle nodes with more than two children.
arrow_right_alt
Modify the input to be a multi-level list instead of a binary tree representation.

help

常见问题

外企场景

继续练习

#572 另一棵树的子树 #538 把二叉搜索树转换为累加树 #530 二叉搜索树的最小绝对差