LeetCode：节点与父节点最大差

题目：

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

来源：力扣（LeetCode）

解：

这道题应该就是用DP，但是一开始思路错了，以为递归传递当前最大差值，但是传递最大差值处理起来比较麻烦，因为我们不仅需要知道当前集构成的最大差值，还需要知道是哪两个节点构成的，否则就会出错。题解中有人是用（子-父）+最大差，其实这是恰好通过而已。考虑一个情况，1->4->3->4，显然在前三个时是正确的，因为恰好构成最大差是1和4，（3-4）+3=2<3。但是到达第四个子代就出错了，(4-3)+3=4>3，那么由1和4（第四子代）就错误了，因为最大差根本就不是第三子代构成的。换句话说，只有当每次DP结点都是最大差两个构成元素之一时，这种DP算法才是正确的。

这里换个DP算法，其实所谓同支节点最大差，就是当前节点跟先前节点中的最大值或最小值的差，所以我们直接把同支节点的最大值和最小值传递下去计算比较就可以了。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.lang.Math; class Solution { private int rs=0; public void dfs(TreeNode node, int max, int min){ if(node==null){ return; } rs=Math.max(Math.abs(max-node.val),rs); rs=Math.max(Math.abs(min-node.val),rs); max=Math.max(max,node.val); min=Math.min(min,node.val); dfs(node.left,max,min); dfs(node.right,max,min); return; } public int maxAncestorDiff(TreeNode root) { dfs(root,root.val,root.val); return rs; } }