1026.节点与其祖先之间的最大差值

链接：1026.节点与其祖先之间的最大差值
难度：Medium
标签：树、深度优先搜索、二叉树
简介：给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

题解 1 - cpp

• 编辑时间：2023-04-18
• 执行用时：8ms
• 内存消耗：14.4MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        function<vector<int>(TreeNode*)> dfs = [&](TreeNode *node) -> vector<int> {
            vector<int> res{ node->val, node->val, 0};
            if (node->left) {
                auto v = dfs(node->left);
                res[0] = min(res[0], v[0]);
                res[1] = max(res[1], v[1]);
                res[2] = max(res[2], max(v[2], max(abs(res[0] - node->val), abs(res[1] - node->val))));
            }
            if (node->right) {
                auto v = dfs(node->right);
                res[0] = min(res[0], v[0]);
                res[1] = max(res[1], v[1]);
                res[2] = max(res[2], max(v[2], max(abs(res[0] - node->val), abs(res[1] - node->val))));
            }
            return res;
        };
        return dfs(root)[2];
    }
};

题解 2 - python

• 编辑时间：2023-04-18
• 执行用时：40ms
• 内存消耗：21.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node: TreeNode) -> List[int]:
            res = [node.val, node.val, 0]
            if node.left != None:
                v = dfs(node.left)
                res[0] = min(res[0], v[0])
                res[1] = max(res[1], v[1])
                res[2] = max(res[2], max(
                    v[2], max(abs(res[0] - node.val), abs(res[1] - node.val))))
            if node.right != None:
                v = dfs(node.right)
                res[0] = min(res[0], v[0])
                res[1] = max(res[1], v[1])
                res[2] = max(res[2], max(
                    v[2], max(abs(res[0] - node.val), abs(res[1] - node.val))))
            return res
        return dfs(root)[2]

题解 3 - rust

• 编辑时间：2023-04-18
• 执行用时：4ms
• 内存消耗：3.2MB
• 编程语言：rust
• 解法介绍：同上。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn max_ancestor_diff(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        use std::cmp::{max, min};
        let root = root.unwrap();
        fn dfs(node: &Rc<RefCell<TreeNode>>) -> Vec<i32> {
            let node = node.as_ref().borrow();
            let mut res = vec![node.val, node.val, 0];
            if node.left.is_some() {
                let v = dfs(&node.left.as_ref().unwrap());
                res[0] = min(res[0], v[0]);
                res[1] = max(res[1], v[1]);
                res[2] = max(
                    res[2],
                    max(
                        v[2],
                        max(i32::abs(res[0] - node.val), i32::abs(res[1] - node.val)),
                    ),
                );
            }
            if node.right.is_some() {
                let v = dfs(&node.right.as_ref().unwrap());
                res[0] = min(res[0], v[0]);
                res[1] = max(res[1], v[1]);
                res[2] = max(
                    res[2],
                    max(
                        v[2],
                        max(i32::abs(res[0] - node.val), i32::abs(res[1] - node.val)),
                    ),
                );
            }
            res
        }
        dfs(&root)[2]
    }
}

题解 4 - python

• 编辑时间：2024-04-05
• 执行用时：46ms
• 内存消耗：18.54MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: TreeNode) -> Tuple[int, int]:
            nonlocal ans
            nmin = nmax = node.val
            if node.left:
                lmin, lmax = dfs(node.left)
                nmin = min(nmin, lmin)
                nmax = max(nmax, lmax)
            if node.right:
                rmin, rmax = dfs(node.right)
                nmin = min(nmin, rmin)
                nmax = max(nmax, rmax)
            ans = max(ans, abs(node.val - nmin), abs(node.val - nmax))
            return [nmin, nmax]
        dfs(root)
        return ans