【leetcode】1026. Maximum Difference Between Node and Ancestor

本文主要是介绍【leetcode】1026. Maximum Difference Between Node and Ancestor，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

   Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b. A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Example 2:

Input: root = [1,null,2,null,0,3]
Output: 3

     这道题的需求是求任意节点和其祖父结点的差值最大值。解题的思路就一句话，这个差值一定是某一路径上最大值和最小值做差得到的，因为在同一路径上的任意两个结点一定互为node和ancestor。 这样就可以用dfs递归维护每一条路径上的最大值最小值，然后在最后一个node上更新result。

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
       // 节点和祖父节点的差距 那就是求同一条路径上的最大值和最小值 
       // 任意一条检索路径上 选取任意两个node 一定互为子父结点
       int res=0;
       digui(root,INT_MIN,INT_MAX,res);
       return res;
        
    }
    void digui(TreeNode* node,int mmax,int mmin,int &res){
        // mmax mmin 为由父结点传递下来的当前路径下的最大值和最小值
        if(node==nullptr) return;
        int mmax_=max(mmax,node->val); //更新路径上的最大值
        int mmin_=min(mmin,node->val); //更新路径上的最小值
        if(node->left!=nullptr){
            digui(node->left,mmax_,mmin_,res);
        }
        if(node->right!=nullptr){
            digui(node->right,mmax_,mmin_,res);
        }
        if(node->left==nullptr && node->right==nullptr){
            int diff=abs(mmax_-mmin_);
            res=max(res,diff);
        }
        return;
    }
};

这篇关于【leetcode】1026. Maximum Difference Between Node and Ancestor的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！