1026. Maximum Difference Between Node and Ancestor(递归+记录最大最小值)

problem:

Given the root of a binary tree, find the maximum value V for which there exists 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: [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.

 

Note:

1. The number of nodes in the tree is between 2 and 5000.
2. Each node will have value between 0 and 100000.

 思路1:

记录父结点到子结点的距离

然后问题就变成：用DFS 求出 root 到 leaf 的最大/小连续子序列（dp便可解决）

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
	int max, min;
	int maxAncestorDiff(TreeNode* root) {
		max = 0;
		min = 0;
		helper(root, root->val, 0, 0);
		return max>abs(min) ? max : abs(min);
	}

	void helper(TreeNode* root, int f, int maxsum, int minsum) {
		if (!root)return;
		maxsum += f - root->val;
		minsum += f - root->val;

		if (max<maxsum)max = maxsum;
		else if (maxsum<0)maxsum = 0;

		if (min>minsum)min = minsum;
		else if (minsum>0)minsum = 0;

		helper(root->left, root->val, maxsum, minsum);
		helper(root->right, root->val, maxsum, minsum);
	}
};

思路2：(一行代码)

 DFS记录遍历路径中最大和最小值，遇到NULL结点，即跑完一条(root->leaf)路径，就求出max - min的值，也就是将这条路径最大差求出来，然后就向上返回。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root,int mx=0,int mn=9999999) {
        return root? max(
            maxAncestorDiff(root->left,max(root->val,mx),min(root->val,mn)),
            maxAncestorDiff(root->right,max(root->val,mx),min(root->val,mn)
            ): mx - mn;
    }
};