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

题目链接

Leetcode.1026 节点与其祖先之间的最大差值 Rating ： 1446

题目描述

给定二叉树的根节点 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^5$

解法：dfs

我们要求的最大差值 $V$ 的两个结点 $A和B$，一定是存在从 根结点 到 叶子节点 某一条路径上的。

我们在向下 递 的过程中，记录路径上的最大结点值 和 最小结点值 $mx和mi$

等到 $root=nullptr$ 时，说明这条路径已经遍历结束，我们就可以更新答案 a n s = m a x { a n s , m x − m i } ans = max \{ans ,mx - mi \} ans=max{ans,mx−mi}。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:
   int ans = 0;

   void dfs(TreeNode* root,int mi,int mx){
       if(root == nullptr){
           ans = max(ans,mx - mi);
           return;
       }

       mi = min(mi,root->val);
       mx = max(mx,root->val);
       dfs(root->left,mi,mx);
       dfs(root->right,mi,mx);
   }
    int maxAncestorDiff(TreeNode* root) {
        dfs(root,root->val,root->val);
        return ans;
    }
};

Python代码：

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:

        def dfs(root,mi,mx):
            nonlocal ans
            if root == None:
                ans = max(ans , mx - mi)
                return

            mx = max(mx,root.val)
            mi = min(mi,root.val)
            dfs(root.left,mi,mx)
            dfs(root.right,mi,mx)

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

        return ans