Sponsored
Sponsored
This approach leverages Depth First Search (DFS) to explore the binary tree. The key idea is to maintain the minimum and maximum values observed along the path from the root to the current node. By comparing the current node's value with these min/max values, we can compute potential maximum differences. As we backtrack, we use these values to determine the maximum difference possible for subtree paths.
Time Complexity: O(n), where n is the number of nodes in the binary tree, because we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursive stack usage.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int maxAncestorDiffHelper(struct TreeNode* node, int minVal, int maxVal) {
11 if (node == NULL) return maxVal - minVal;
12 minVal = (node->val < minVal) ? node->val : minVal;
13 maxVal = (node->val > maxVal) ? node->val : maxVal;
14 int leftDiff = maxAncestorDiffHelper(node->left, minVal, maxVal);
15 int rightDiff = maxAncestorDiffHelper(node->right, minVal, maxVal);
16 return (leftDiff > rightDiff) ? leftDiff : rightDiff;
17}
18
19int maxAncestorDiff(struct TreeNode* root) {
20 if (root == NULL) return 0;
21 return maxAncestorDiffHelper(root, root->val, root->val);
22}The function maxAncestorDiffHelper is a recursive helper function that traverses the binary tree using DFS. It keeps track of the current path's minimum and maximum values as parameters. At each node, it updates these values and calculates differences, eventually returning the maximum found.
This approach utilizes an iterative Breadth First Search (BFS) paradigm using a queue to traverse the tree. Queue elements consist of a node and associated min/max values for the path leading to this node. As nodes are processed, the difference between node values and min/max path values are calculated to find the maximum difference.
Time Complexity: O(n), as each node is visited once.
Space Complexity: O(n), for the queue storing the nodes in the worst case (when the tree is bushy).
1from collections import deque
2
3class Solution:
4 def In this solution, a queue is used for BFS traversal, storing node and path min/max values. For each node, we compute current possible differences and keep track of the maximum difference encountered. The solution efficiently processes tree traversal iteratively.