【每日一题Day181】LC1026节点与其祖先之间的最大差值 | 树形dp

简介: 【每日一题Day181】LC1026节点与其祖先之间的最大差值 | 树形dp

节点与其祖先之间的最大差值【LC1026】

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

(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)

慢慢来~

yiyiyi 没发出去

树形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),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 <= mx
        mn = 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


目录
相关文章
|
7月前
【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归
【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归
49 0
|
7月前
|
人工智能 BI
【每日一题Day232】LC2699修改图中的边权 |最短路径
【每日一题Day232】LC2699修改图中的边权 |最短路径
42 0
|
7月前
【每日一题Day144】LC1617统计子树中城市之间最大距离 | 树形dp
【每日一题Day144】LC1617统计子树中城市之间最大距离 | 树形dp
35 0
|
7月前
|
人工智能 BI
【每日一题Day267】LC834树中距离之和 | 换根dp
【每日一题Day267】LC834树中距离之和 | 换根dp
49 0
|
7月前
【每日一题Day300】LC2236判断根结点是否等于子结点之和
【每日一题Day300】LC2236判断根结点是否等于子结点之和
36 0
|
7月前
【每日一题Day305】LC1448统计二叉树中好节点的数目 | dfs
【每日一题Day305】LC1448统计二叉树中好节点的数目 | dfs
46 0
|
7月前
|
索引
【每日一题Day131】LC1144递减元素使数组呈锯齿状 | 贪心+枚举
【每日一题Day131】LC1144递减元素使数组呈锯齿状 | 贪心+枚举
50 0
|
索引
【Leetcode -1721.交换链表中的节点 -2058.找出临界点之间的最小和最大距离】
【Leetcode -1721.交换链表中的节点 -2058.找出临界点之间的最小和最大距离】
49 0
|
7月前
|
人工智能 BI
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
60 0
|
7月前
|
算法
【每日一题Day235】LC1483树节点的第 K 个祖先 | 倍增
【每日一题Day235】LC1483树节点的第 K 个祖先 | 倍增
54 1