Update Maximum Difference Between Node and Ancestor.java

varunu28 · web-flow · commit c8738e752f5a · 2022-12-08T17:18:06.000-08:00
diff --git a/Medium/Maximum Difference Between Node and Ancestor.java b/Medium/Maximum Difference Between Node and Ancestor.java
@@ -14,16 +14,38 @@
  * }
  */
 class Solution {
-  public int maxAncestorDiff(TreeNode root) {
-    return dfs(root, root.val, root.val);
-  }
-  
-  private int dfs(TreeNode root, int min, int max) {
-    if (root == null) {
-      return max - min;
+    public int maxAncestorDiff(TreeNode root) {
+        int maxDiff = 0;
+        Queue<NodeValuePair> queue = new LinkedList<>();
+        queue.add(new NodeValuePair(root, root.val, root.val));
+        while (!queue.isEmpty()) {
+            NodeValuePair removed = queue.remove();
+            TreeNode node = removed.node;
+            Integer minNodeValue = removed.minNodeValue;
+            Integer maxNodeValue = removed.maxNodeValue;
+            maxDiff = Math.max(maxDiff, Math.max(Math.abs(node.val - minNodeValue), Math.abs(node.val - maxNodeValue)));
+            Integer updatedMinNodeValue = Math.min(node.val, minNodeValue);
+            Integer updatedMaxNodeValue = Math.max(node.val, maxNodeValue);
+            if (node.left != null) {
+                queue.add(new NodeValuePair(node.left, updatedMinNodeValue, updatedMaxNodeValue));
+            }
+            if (node.right != null) {
+                queue.add(new NodeValuePair(node.right, updatedMinNodeValue, updatedMaxNodeValue));
+            }
+        }
+        return maxDiff;
+    }
+    
+    
+    private static class NodeValuePair {
+        private TreeNode node;
+        private Integer minNodeValue;
+        private Integer maxNodeValue;
+        
+        public NodeValuePair(TreeNode node, Integer minNodeValue, Integer maxNodeValue) {
+            this.node = node;
+            this.minNodeValue = minNodeValue;
+            this.maxNodeValue = maxNodeValue;
+        }
     }
-    max = Math.max(root.val, max);
-    min = Math.min(root.val, min);
-    return Math.max(dfs(root.left, min, max), dfs(root.right, min, max));
-  }
 }
