This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

describe

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:

Input: root = [14, 8,3,10,1,6, null, 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.Copy the code

Example 2:

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

Note:

The number of nodes in the tree is in the range [2, 5000].
0 <= Node.val <= 10^5
Copy the code

parsing

Given a binary tree, calculate the maximum absolute difference between the ancestor node and any of its children. The idea is relatively simple. In fact, for each leaf node, the maximum difference is the difference between its maximum and minimum value to the root node:

  • Define recursive function DFS to calculate the maximum difference between the root node and the current node. There are three parameters, the first parameter is root of the current node, and the second and third parameters record the minimum value mn and maximum value mx on the path from the root node to the current node.
  • Mx-mn is calculated when a leaf node is encountered, otherwise DFS is continuously called in the left and right subtrees to find the maximum value
  • The answer is at the end of the recursion

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def maxAncestorDiff(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(root, mn, mx):
            if not root: return mx-mn
            mn = min(mn, root.val)
            mx = max(mx, root.val)
            left = dfs(root.left, mn, mx)
            right = dfs(root.right, mn, mx)
            return max(left, right)
        return dfs(root, root.val, root.val)
        	      
		
Copy the code

The results

Runtime: 10 ms, faster than 72.18% of Python online submissions for Maximum Difference Between nodes and yields. Memory Usage: Submissions in the Python online submissions for Maximum Difference Between nodes and yields.Copy the code

parsing

  • Use the result variable to record the maximum absolute difference
  • The recursive function DFS is defined to calculate the maximum difference between the root node and the current node. There are three parameters, the first parameter is root of the current node, and the second and third parameters record the minimum value mn and maximum value mx on the path from the root node to the current node. DFS is recursively called in the left and right subtrees to update result
  • When the recursion ends, the result is the answer

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def maxAncestorDiff(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.result = 0
        def dfs(node, cur_max, cur_min):
            if not node:
                return
            self.result = max(self.result, abs(cur_max-node.val), abs(cur_min-node.val))
            cur_max = max(cur_max, node.val)
            cur_min = min(cur_min, node.val)
            dfs(node.left, cur_max, cur_min)
            dfs(node.right, cur_max, cur_min)

        dfs(root, root.val, root.val)
        return self.result
        
Copy the code

The results

Runtime: 10 ms, faster than 50.38% of Python online submissions for Maximum Difference Between nodes and yields. Submissions in Python online submissions for Maximum Difference Between nodes and yields.Copy the code

Original link: leetcode.com/problems/ma…

Your support is my biggest motivation