Formatted question description: https://leetcode.ca/all/1026.html

1026. Maximum Difference Between Node and Ancestor (Medium)

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:

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

Related Topics:
Tree, Depth-first Search

Solution 1. Post-order traversal

// OJ: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    pair<int, int> dfs(TreeNode *root) {
        if (!root) return { INT_MAX, INT_MIN };
        auto [lmin, lmax] = dfs(root->left);
        auto [rmin, rmax] = dfs(root->right);
        int mn = min({ root->val, lmin, rmin }), mx = max({ root->val, lmax, rmax });
        ans = max({ ans, abs(root->val - mn), abs(mx - root->val) });
        return { mn, mx };
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

Solution 2.

When traversing down, we update the min and max values we’ve seen from the root to the current node.

At the null pointers of the leave nodes, we calculate the difference between the max and min values we’ve seen since the root.

When traversing up, we return the maximum of the results for the left subtree and the right subtree.

// OJ: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// Time: O(N)
// Space: O(H)
class Solution {
    int dfs(TreeNode *root, int mn, int mx) {
        if (!root) return mx - mn;
        mn = min(mn, root->val);
        mx = max(mx, root->val);
        return max(dfs(root->left, mn, mx), dfs(root->right, mn, mx));
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        Map<TreeNode, int[]> nodeValuesMap = new HashMap<TreeNode, int[]>();
        List<TreeNode> nodesList = new ArrayList<TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int value = node.val;
            nodesList.add(node);
            nodeValuesMap.put(node, new int[]{value, value});
            TreeNode left = node.left, right = node.right;
            if (left != null)
                queue.offer(left);
            if (right != null)
                queue.offer(right);
        }
        int maxDifference = 0;
        for (int i = nodesList.size() - 1; i >= 0; i--) {
            TreeNode node = nodesList.get(i);
            int value = node.val;
            int[] values = nodeValuesMap.get(node);
            TreeNode left = node.left, right = node.right;
            if (left != null) {
                int[] leftValues = nodeValuesMap.get(left);
                maxDifference = Math.max(maxDifference, Math.max(Math.abs(value - leftValues[0]), Math.abs(value - leftValues[1])));
                values[0] = Math.min(values[0], leftValues[0]);
                values[1] = Math.max(values[1], leftValues[1]);
            }
            if (right != null) {
                int[] rightValues = nodeValuesMap.get(right);
                maxDifference = Math.max(maxDifference, Math.max(Math.abs(value - rightValues[0]), Math.abs(value - rightValues[1])));
                values[0] = Math.min(values[0], rightValues[0]);
                values[1] = Math.max(values[1], rightValues[1]);
            }
        }
        return maxDifference;
    }
}

############

/**
 * 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;

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

    private void dfs(TreeNode root, int mi, int mx) {
        if (root == null) {
            return;
        }
        int x = Math.max(Math.abs(mi - root.val), Math.abs(mx - root.val));
        ans = Math.max(ans, x);
        mi = Math.min(mi, root.val);
        mx = Math.max(mx, root.val);
        dfs(root.left, mi, mx);
        dfs(root.right, mi, mx);
    }
}

// OJ: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    pair<int, int> dfs(TreeNode *root) {
        if (!root) return { INT_MAX, INT_MIN };
        auto [lmin, lmax] = dfs(root->left);
        auto [rmin, rmax] = dfs(root->right);
        int mn = min({ root->val, lmin, rmin }), mx = max({ root->val, lmax, rmax });
        ans = max({ ans, abs(root->val - mn), abs(mx - root->val) });
        return { mn, mx };
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

# 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:
        def dfs(root, mi, mx):
            if root is None:
                return
            nonlocal ans
            ans = max(ans, abs(mi - root.val), abs(mx - root.val))
            mi = min(mi, root.val)
            mx = max(mx, root.val)
            dfs(root.left, mi, mx)
            dfs(root.right, mi, mx)

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

############

# 1026. Maximum Difference Between Node and Ancestor
# https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

# 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:
        
        def dfs(node, low, high):
            if not node: return high - low
            
            low = min(low, node.val)
            high = max(high, node.val)
            
            return max(dfs(node.left, low, high), dfs(node.right, low, high))
        
        return dfs(root, root.val, root.val)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxAncestorDiff(root *TreeNode) (ans int) {
	var dfs func(*TreeNode, int, int)
	dfs = func(root *TreeNode, mi, mx int) {
		if root == nil {
			return
		}
		ans = max(ans, max(abs(mi-root.Val), abs(mx-root.Val)))
		mi = min(mi, root.Val)
		mx = max(mx, root.Val)
		dfs(root.Left, mi, mx)
		dfs(root.Right, mi, mx)
	}
	dfs(root, root.Val, root.Val)
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

/**
 * 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 = (root, mi, mx) => {
        if (!root) {
            return;
        }
        ans = Math.max(ans, Math.abs(mi - root.val), Math.abs(mx - root.val));
        mi = Math.min(mi, root.val);
        mx = Math.max(mx, root.val);
        dfs(root.left, mi, mx);
        dfs(root.right, mi, mx);
    };
    dfs(root, root.val, root.val);
    return ans;
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxAncestorDiff(root: TreeNode | null): number {
    const dfs = (root: TreeNode | null, mi: number, mx: number): void => {
        if (!root) {
            return;
        }
        ans = Math.max(ans, Math.abs(root.val - mi), Math.abs(root.val - mx));
        mi = Math.min(mi, root.val);
        mx = Math.max(mx, root.val);
        dfs(root.left, mi, mx);
        dfs(root.right, mi, mx);
    };
    let ans: number = 0;
    dfs(root, root.val, root.val);
    return ans;
}

1026 - Maximum Difference Between Node and Ancestor

1026. Maximum Difference Between Node and Ancestor (Medium)

Solution 1. Post-order traversal

Solution 2.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1026. Maximum Difference Between Node and Ancestor (Medium)

Solution 1. Post-order traversal

Solution 2.

All Problems

All Solutions