LeetCode 1026: Maximum Difference Between Node and Ancestor (DFS Path Min/Max Tracking)

2026-03-25 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 1026Binary TreeDFS

Today we solve LeetCode 1026 - Maximum Difference Between Node and Ancestor.

Source: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

LeetCode 1026 maximum difference between node and ancestor path min max diagram

English

Problem Summary

Given a binary tree, choose any node a and any descendant b of a. We need the maximum value of |a.val - b.val| over all such ancestor-descendant pairs.

Key Insight

For each root-to-current path, only two numbers matter: the minimum value and maximum value seen so far on that path. At node x, the best ancestor gap involving x is max(|x-minPath|, |x-maxPath|). So we propagate path min/max with DFS.

Brute Force and Limitations

Brute force checks every node against all descendants, which can degrade to O(n^2) on skewed trees. This is too slow for larger inputs.

Optimal Algorithm Steps (DFS with Path Range)

1) Start DFS from root carrying pathMin = root.val, pathMax = root.val.
2) At each node, update answer with max(abs(node.val-pathMin), abs(node.val-pathMax)).
3) Update path range: newMin = min(pathMin, node.val), newMax = max(pathMax, node.val).
4) Recurse into left and right children with the updated range.
5) The global maximum is the result.

Complexity Analysis

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

Common Pitfalls

- Comparing only parent-child differences instead of ancestor-descendant differences.
- Forgetting to carry both min and max along the path.
- Updating path range after recursion rather than before passing to children.
- Returning local subtree result without taking global maximum.

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 ans = 0;

    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return ans;
    }

    private void dfs(TreeNode node, int pathMin, int pathMax) {
        if (node == null) return;

        ans = Math.max(ans, Math.max(Math.abs(node.val - pathMin), Math.abs(node.val - pathMax)));

        int newMin = Math.min(pathMin, node.val);
        int newMax = Math.max(pathMax, node.val);

        dfs(node.left, newMin, newMax);
        dfs(node.right, newMin, newMax);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxAncestorDiff(root *TreeNode) int {
    ans := 0

    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, pathMin int, pathMax int) {
        if node == nil {
            return
        }

        d1 := node.Val - pathMin
        if d1 < 0 {
            d1 = -d1
        }
        d2 := node.Val - pathMax
        if d2 < 0 {
            d2 = -d2
        }
        if d1 > ans {
            ans = d1
        }
        if d2 > ans {
            ans = d2
        }

        newMin := pathMin
        if node.Val < newMin {
            newMin = node.Val
        }
        newMax := pathMax
        if node.Val > newMax {
            newMax = node.Val
        }

        dfs(node.Left, newMin, newMax)
        dfs(node.Right, newMin, newMax)
    }

    dfs(root, root.Val, root.Val)
    return ans
}

/**
 * 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 ans = 0;

    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return ans;
    }

    void dfs(TreeNode* node, int pathMin, int pathMax) {
        if (!node) return;

        ans = max(ans, max(abs(node->val - pathMin), abs(node->val - pathMax)));

        int newMin = min(pathMin, node->val);
        int newMax = max(pathMax, node->val);

        dfs(node->left, newMin, newMax);
        dfs(node->right, newMin, newMax);
    }
};

# 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:
        ans = 0

        def dfs(node: Optional[TreeNode], path_min: int, path_max: int) -> None:
            nonlocal ans
            if not node:
                return

            ans = max(ans, abs(node.val - path_min), abs(node.val - path_max))

            new_min = min(path_min, node.val)
            new_max = max(path_max, node.val)

            dfs(node.left, new_min, new_max)
            dfs(node.right, new_min, new_max)

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

/**
 * 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)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxAncestorDiff = function(root) {
  let ans = 0;

  const dfs = (node, pathMin, pathMax) => {
    if (!node) return;

    ans = Math.max(ans, Math.abs(node.val - pathMin), Math.abs(node.val - pathMax));

    const newMin = Math.min(pathMin, node.val);
    const newMax = Math.max(pathMax, node.val);

    dfs(node.left, newMin, newMax);
    dfs(node.right, newMin, newMax);
  };

  dfs(root, root.val, root.val);
  return ans;
};

中文

题目概述

给定一棵二叉树，任选祖先节点 a 与其后代节点 b，要求最大化 |a.val - b.val|，返回这个最大值。

核心思路

在任意“根到当前节点”的路径上，真正有用的信息只有两个：路径最小值和路径最大值。当前节点与祖先的最大差值只可能来自这两个边界，因此 DFS 过程中持续维护 pathMin/pathMax 即可。

基线解法与不足

暴力做法是对每个节点向下枚举全部后代并计算差值，最坏会到 O(n^2)（链状树）。规模稍大就容易超时。

最优算法步骤（DFS + 路径最值）

1）从根节点开始 DFS，初始化 pathMin = pathMax = root.val。
2）在节点 x 处，用 max(|x-pathMin|, |x-pathMax|) 更新答案。
3）更新路径边界：newMin = min(pathMin, x)，newMax = max(pathMax, x)。
4）把更新后的边界继续传给左右子树。
5）遍历结束后，全局最大值即答案。

复杂度分析

时间复杂度：O(n)（每个节点访问一次）。
空间复杂度：O(h)（递归栈深度，h 为树高）。

常见陷阱

- 只比较父子差值，忽略“祖先-后代”跨层关系。
- 路径上传递了最小值却忘了同时传最大值。
- 先递归再更新路径边界，导致子树拿到错误状态。
- 只返回局部结果，没有维护全局最大值。

多语言参考实现（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 ans = 0;

    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return ans;
    }

    private void dfs(TreeNode node, int pathMin, int pathMax) {
        if (node == null) return;

        ans = Math.max(ans, Math.max(Math.abs(node.val - pathMin), Math.abs(node.val - pathMax)));

        int newMin = Math.min(pathMin, node.val);
        int newMax = Math.max(pathMax, node.val);

        dfs(node.left, newMin, newMax);
        dfs(node.right, newMin, newMax);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxAncestorDiff(root *TreeNode) int {
    ans := 0

    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, pathMin int, pathMax int) {
        if node == nil {
            return
        }

        d1 := node.Val - pathMin
        if d1 < 0 {
            d1 = -d1
        }
        d2 := node.Val - pathMax
        if d2 < 0 {
            d2 = -d2
        }
        if d1 > ans {
            ans = d1
        }
        if d2 > ans {
            ans = d2
        }

        newMin := pathMin
        if node.Val < newMin {
            newMin = node.Val
        }
        newMax := pathMax
        if node.Val > newMax {
            newMax = node.Val
        }

        dfs(node.Left, newMin, newMax)
        dfs(node.Right, newMin, newMax)
    }

    dfs(root, root.Val, root.Val)
    return ans
}

/**
 * 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 ans = 0;

    int maxAncestorDiff(TreeNode* root) {
        dfs(root, root->val, root->val);
        return ans;
    }

    void dfs(TreeNode* node, int pathMin, int pathMax) {
        if (!node) return;

        ans = max(ans, max(abs(node->val - pathMin), abs(node->val - pathMax)));

        int newMin = min(pathMin, node->val);
        int newMax = max(pathMax, node->val);

        dfs(node->left, newMin, newMax);
        dfs(node->right, newMin, newMax);
    }
};

# 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:
        ans = 0

        def dfs(node: Optional[TreeNode], path_min: int, path_max: int) -> None:
            nonlocal ans
            if not node:
                return

            ans = max(ans, abs(node.val - path_min), abs(node.val - path_max))

            new_min = min(path_min, node.val)
            new_max = max(path_max, node.val)

            dfs(node.left, new_min, new_max)
            dfs(node.right, new_min, new_max)

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

/**
 * 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)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxAncestorDiff = function(root) {
  let ans = 0;

  const dfs = (node, pathMin, pathMax) => {
    if (!node) return;

    ans = Math.max(ans, Math.abs(node.val - pathMin), Math.abs(node.val - pathMax));

    const newMin = Math.min(pathMin, node.val);
    const newMax = Math.max(pathMax, node.val);

    dfs(node.left, newMin, newMax);
    dfs(node.right, newMin, newMax);
  };

  dfs(root, root.val, root.val);
  return ans;
};