5030-节点与其祖先之间的最大差值

前言Weekly Contest 132的 节点与其祖先之间的最大差值：给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）示例：输入：[8,3,10,1,6,null,14,null,null,4,7,13]输出：7解释： 我们有大量的节点与其祖先的差值，其中一些如下：|8 - 3| = 5|3 - 7| = 4|8 - 1| = 7|10 - 13| = 3在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。提示：树中的节点数在 2 到 5000 之间。每个节点的值介于 0 到 100000 之间。解题思路本题需要将问题分解一下，首先先实现根节点与每个节点的差值的最大值的算法，然后只需要遍历每个子树即可。实现代码 /** * 5030. 节点与其祖先之间的最大差值 * @param root * @return / public int maxAncestorDiff(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int max=0; while(!queue.isEmpty()){//层序遍历 TreeNode node=queue.poll(); max=Math.max(max,getMaxDiffByRoot(node)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; } /* * 获取某个根节点下所有节点与根节点的差值的最大值 * 这里选择使用层序遍历 * @param root * @return */ private int getMaxDiffByRoot(TreeNode root){ Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); //根节点的值，用于比较 int rootValue=root.val; //最大差值 int max=0; while(!queue.isEmpty()){//层序遍历每个节点 TreeNode node=queue.poll(); // 获取最大值 max=Math.max(max,Math.abs(node.val-rootValue)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; }