【每日一题Day181】LC1026节点与其祖先之间的最大差值 | 树形dp
节点与其祖先之间的最大差值【LC1026】
给定二叉树的根节点
root
,找出存在于 不同 节点A
和B
之间的最大值V
,其中V = |A.val - B.val|
,且A
是B
的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)
慢慢来~
树形dp[归]
-
思路:
某个祖先节点与其子节点的最大差值,取决于其左右子树的最小值和最大值与其的差值,因此可以采用树形dp的形式,将每颗子树的最小值最大值返回给祖先节点。每遍历一个节点,判断其是否有孩子节点,有则需要判断是否需要更新答案
-
实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/// 树形dp 返回当前子树的最大值和最小值 class Solution {int res = 0;public int maxAncestorDiff(TreeNode root) {dfs(root);return res;}public int[] dfs(TreeNode root){if (root == null){return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};} int[] left = dfs(root.left);int[] right = dfs(root.right);if (root.left != null){res = Math.max(res, Math.max(Math.abs(left[0] - root.val), Math.abs(left[1] - root.val)));}if (root.right != null){res = Math.max(res, Math.max(Math.abs(right[0] - root.val), Math.abs(right[1] - root.val)));}// 求当前子树的最小值和最大值int[] cur = {root.val, root.val};cur[0] = Math.min(cur[0], Math.min(left[0], right[0]));cur[1] = Math.max(cur[1], Math.max(left[1], right[1]));return cur;} }
- 复杂度
- 时间复杂度:O(n)O(n)O(n),n为节点数目
- 空间复杂度:O(n)O(n)O(n),空间复杂度主要取决于递归调用层数,最大层数等于二叉树的高度,最坏情况下,二叉树的高度等于二叉树中的节点个数。
- 复杂度
[递]
-
思路
也可以记录祖先节点的最大值和最小值
-
实现
class Solution {private int ans;public int maxAncestorDiff(TreeNode root) {dfs(root, root.val, root.val);return ans;}private void dfs(TreeNode node, int mn, int mx) {if (node == null) return;// 虽然题目要求「不同节点」,但是相同节点的差值为 0,不会影响最大差值// 所以先更新 mn 和 mx,再计算差值也是可以的// 在这种情况下,一定满足 mn <= node.val <= mxmn = Math.min(mn, node.val);mx = Math.max(mx, node.val);ans = Math.max(ans, Math.max(node.val - mn, mx - node.val));dfs(node.left, mn, mx);dfs(node.right, mn, mx);} }作者:灵茶山艾府 链接:https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/solutions/2232367/liang-chong-fang-fa-zi-ding-xiang-xia-zi-wj9v/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
-
优化:在遍历到叶子节点的时候再更新答案
class Solution {private int ans;public int maxAncestorDiff(TreeNode root) {dfs(root, root.val, root.val);return ans;}private void dfs(TreeNode node, int mn, int mx) {if (node == null) {ans = Math.max(ans, mx - mn);return;}mn = Math.min(mn, node.val);mx = Math.max(mx, node.val);dfs(node.left, mn, mx);dfs(node.right, mn, mx);} }作者:灵茶山艾府 链接:https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/solutions/2232367/liang-chong-fang-fa-zi-ding-xiang-xia-zi-wj9v/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。