How do I approach the Maximum Difference Between Node and Ancestor problem?

Use a DFS traversal while tracking the minimum and maximum values at each node to find the maximum absolute difference between ancestor and descendant nodes.

What is the time complexity of the Maximum Difference Between Node and Ancestor problem?

The time complexity is O(n), where `n` is the number of nodes, as each node is visited exactly once during DFS traversal.

Can this problem be solved iteratively?

Yes, it can be solved iteratively using a stack to simulate the recursive DFS approach.

How does the ancestor relationship affect the solution?

The ancestor relationship is crucial because it ensures that the value difference must always be between a node and its ancestor, not just any two nodes.

What is the space complexity of this solution?

The space complexity is O(h), where `h` is the height of the tree, due to the recursion stack. In the worst case, `h` can be O(n) for a skewed tree.

#1026

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

节点与其祖先之间的最大差值

给定二叉树的根节点 root ，找出存在于不同节点 A 和 B 之间的最大值 V ，其中 V = |A.val - B.val| ，且 A 是 B 的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）示例 1：输入： root…

树深度优先搜索二叉树

题目描述

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

提示：

树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 10⁵

lightbulb

解题思路

方法一：DFS

对于每个节点，求其与祖先节点的最大差值，我们只需要求出该节点与祖先节点最大值和最小值的差值。取所有节点与祖先节点差值的最大值即可。

因此，我们设计一个函数 $dfs(root, mi, mx)$ ，表示当前搜索到的节点为 $root$ ，其祖先节点的最大值为 $mx$ ，最小值为 $mi$ ，函数内更新最大差值 $ans$ 。

函数 $dfs(root, mi, mx)$ 的逻辑如下：

若 $root$ 为空，直接返回。
否则，我们更新 $ans = max(ans, |mi - root.val|, |mx - root.val|)$ 。
然后更新 $mi = min(mi, root.val)$ , $mx = max(mx, root.val)$ ，并且递归搜索左右子树。

在主函数中，我们调用 $dfs(root, root.val, root.val)$ ，最后返回 $ans$ 即可。

时间复杂度 $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

21

22

# 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 maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode], mi: int, mx: int):
            if root is None:
                return
            nonlocal ans
            ans = max(ans, abs(mi - root.val), abs(mx - root.val))
            mi = min(mi, root.val)
            mx = max(mx, root.val)
            dfs(root.left, mi, mx)
            dfs(root.right, mi, mx)

        ans = 0
        dfs(root, root.val, root.val)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a clear understanding of tree traversal and recursive solutions.
question_mark
Ensure the candidate can explain how state tracking is essential for finding the maximum difference.
question_mark
Evaluate if the candidate can optimize the solution and explain the trade-offs of space and time complexities.

warning

常见陷阱

外企场景

error
Failing to correctly track both the minimum and maximum values as you traverse down the tree.
error
Misunderstanding the ancestor relationship, which could lead to incorrect calculations of the node differences.
error
Not handling edge cases such as very small or unbalanced trees effectively.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding the maximum difference between nodes for a non-binary tree structure.
arrow_right_alt
Implementing the solution iteratively without recursion.
arrow_right_alt
Handling a tree where the node values are all the same, potentially simplifying the problem.

help

常见问题

外企场景

继续练习

#1028 从先序遍历还原二叉树 #1022 从根到叶的二进制数之和 #1038 从二叉搜索树到更大和树