LeetCode - Medium - 1026. Maximum Difference Between Node and Ancestor

不念不忘少年蓝@ 2022-10-08 15:27 20阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[LeetCode - Medium - 1026. Maximum Difference Between Node and Ancestor][]

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

![d3fa6751dc1d9dad31dd5029d5888b5c.png][]

Input: root = [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.

**Example 2:**

![1ec80a9e3b12ce1187e2ad1e0d99de48.png][]

Input: root = [1,null,2,null,0,3]
    Output: 3

**Constraints:**

*  The number of nodes in the tree is in the range \[2, 5000\].
 *   0 < = N o d e . v a l < = 1 0 5 0 <= Node.val <= 10^5 0<=Node.val<=105

## Analysis ##

遍历从根节点到叶子节点的路径中，找出最大值和最小值，便得到这路径的最大差值，以此类推，从各个从根节点到叶子节点的路径的最大差值中求出最大值。

方法一：我自己写的，后序遍历模式。

方法二：我自己写的，前序遍历模式。

方法三：别人写的，后序遍历模式，更精明简要。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class MaximumDifferenceBetweenNodeAndAncestor { 
    	
    	//方法一：我自己写的，后序遍历模式
        public int maxAncestorDiff(TreeNode root) { 
        	return maxAncestorDiff(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        
        private int maxAncestorDiff(TreeNode node, int max, int min) { 
        	max = Math.max(max, node.val);
        	min = Math.min(min, node.val);
        	int maxDiff = max - min;
        		
        	int maxDiffFromLeft = Integer.MIN_VALUE;
        	if(node.left != null) { 
        		maxDiffFromLeft = maxAncestorDiff(node.left, max, min);
        	}
        	
        	int maxDiffFromRight = Integer.MIN_VALUE;
        	if(node.right != null) { 
        		maxDiffFromRight = maxAncestorDiff(node.right, max, min);
        	}
        	    	
        	return Math.max(Math.max(maxDiffFromLeft, maxDiffFromRight), maxDiff);
        }
        
        //方法二：我自己写的，前序遍历模式
        public int maxAncestorDiff2(TreeNode root) { 
        	int[] maxDiff = { Integer.MIN_VALUE};
        	maxAncestorDiff2(root, Integer.MIN_VALUE, Integer.MAX_VALUE, maxDiff);
        	return maxDiff[0];
        }
    
    	private void maxAncestorDiff2(TreeNode node, int max, int min, int[] maxDiff) { 
    		if(node == null) return;
        	max = Math.max(max, node.val);
        	min = Math.min(min, node.val);
        	maxDiff[0] = Math.max(maxDiff[0], max - min);
    		maxAncestorDiff2(node.left, max, min, maxDiff);
    		maxAncestorDiff2(node.right, max, min, maxDiff);
    	}
    
    	
    	//方法三：别人写的，后序遍历模式，更精明简要
        public int maxAncestorDiff3(TreeNode root) { 
            return dfs(root, root.val, root.val);
        }
    
        public int dfs(TreeNode root, int mn, int mx) { 
            if (root == null) return mx - mn;
            mx = Math.max(mx, root.val);
            mn = Math.min(mn, root.val);
            return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
        }
    	
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class MaximumDifferenceBetweenNodeAndAncestorTest { 
    
        @Test
        public void test() { 
            MaximumDifferenceBetweenNodeAndAncestor mObj = new MaximumDifferenceBetweenNodeAndAncestor();
    
            TreeNode root1 = BinaryTree.integers2BinaryTree(8,3,10,1,6,null,14,null,null,4,7,13);
            assertEquals(7, mObj.maxAncestorDiff(root1));
            
            TreeNode root2 = BinaryTree.integers2BinaryTree(1,null,2,null,0,3);
            assertEquals(3, mObj.maxAncestorDiff(root2));
        }
        
        @Test
        public void test2() { 
        	MaximumDifferenceBetweenNodeAndAncestor mObj = new MaximumDifferenceBetweenNodeAndAncestor();
        	
        	TreeNode root1 = BinaryTree.integers2BinaryTree(8,3,10,1,6,null,14,null,null,4,7,13);
        	assertEquals(7, mObj.maxAncestorDiff2(root1));
        	
        	TreeNode root2 = BinaryTree.integers2BinaryTree(1,null,2,null,0,3);
        	assertEquals(3, mObj.maxAncestorDiff2(root2));
        }
        
        @Test
        public void test3() { 
        	MaximumDifferenceBetweenNodeAndAncestor mObj = new MaximumDifferenceBetweenNodeAndAncestor();
        	
        	TreeNode root1 = BinaryTree.integers2BinaryTree(8,3,10,1,6,null,14,null,null,4,7,13);
        	assertEquals(7, mObj.maxAncestorDiff3(root1));
        	
        	TreeNode root2 = BinaryTree.integers2BinaryTree(1,null,2,null,0,3);
        	assertEquals(3, mObj.maxAncestorDiff3(root2));
        }
    }

[LeetCode - Medium - 1026. Maximum Difference Between Node and Ancestor]: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
[d3fa6751dc1d9dad31dd5029d5888b5c.png]: /images/20221005/3fb328ead7cb408b9bf27c6727e0eebd.png
[1ec80a9e3b12ce1187e2ad1e0d99de48.png]: /images/20221005/585f2a9e692a46b2b6b9a19ee48c4c32.png