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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
6 this.val = val;
7 this.left = left;
8 this.right = right;
9 }
10}
11
12public class Solution {
13 public int MaxAncestorDiff(TreeNode root) {
14 return Dfs(root, root.val, root.val);
15 }
16
17 private int Dfs(TreeNode node, int minVal, int maxVal) {
18 if (node == null) return maxVal - minVal;
19 minVal = Math.Min(minVal, node.val);
20 maxVal = Math.Max(maxVal, node.val);
21 int leftDiff = Dfs(node.left, minVal, maxVal);
22 int rightDiff = Dfs(node.right, minVal, maxVal);
23 return Math.Max(leftDiff, rightDiff);
24 }
25}The C# solution uses recursion to navigate each node with the Dfs function, keeping track of leading path min/max values, and evaluating differences.
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.