Leetcode 1026. Maximum Difference Between Node and Ancestor

tags: Leetcode(C++)

題目 : https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/ 。

想法 : 記錄每一個子樹擁有的最大子孫與最小子孫，並同時與子樹根節點做相減運算後是否得到答案，往上直到最上方的根結點。

時間複雜度 : O(n)，有可能是一條鏈。

程式碼 :

/**
 * 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 Max_Travel(TreeNode* root){
        if(root == nullptr) return -1;
        
        int n1=Max_Travel(root->left);
        int n2=Max_Travel(root->right);
        
        if(n1 != -1) ans=max(ans,abs(root->val-n1));
        if(n2 != -1) ans=max(ans,abs(root->val-n2));
        
        return max(n1,max(n2,root->val));
    }
    
    int Min_Travel(TreeNode* root){
        if(root == nullptr) return 100010;
        
        int n1=Min_Travel(root->left);
        int n2=Min_Travel(root->right);
        
        if(n1 != 100010) ans=max(ans,abs(root->val-n1));
        if(n2 != 100010) ans=max(ans,abs(root->val-n2));
        
        return min(n1,min(n2,root->val));
    }    

    
    int maxAncestorDiff(TreeNode* root) {
        int maxn=Max_Travel(root),mini=Min_Travel(root);
        
        cout << ans << " " << maxn << " " << mini << "\n";
        ans=max(ans,max(abs(root->val-maxn),abs(root->val-mini)));
        return ans;
    }
};