深度优先搜索（只阐述二叉树递归遍历）中的参数传递问题

本文链接：https://blog.csdn.net/addyysn/article/details/130228255

文章讨论了如何解决LeetCode上的一个关于二叉树的问题，要求找到两个不同节点之间的最大值差，其中一个节点是另一个的祖先。作者提到，使用递归的方法，通过维护当前子树的最小值和最大值来更新全局最大差值，可以有效地解决这个问题。递归过程中避免了参数混淆，提高了代码的清晰度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

2023年4月18日，今天Leetcode的每日一题是节点与其祖先之间的最大值，通过率达到了百分之70多，实际上在中等难度的每日一题中，这算是很低的通过率了！

题目是这样子的：

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

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

个人得思路是灵神题解的递的解法，因为这涉及到不同子树之间的分开的关系，因此自己想要使用的vector数组存储节点然后每次for循环从下标0开始进行遍历比较，实际上并不好实现，因为一旦进入到某个子树的尽头，那么返回的话该子树根节点时要删除子树所有push进入vector中的元素。

灵神的递的解法是：

进行递归遍历子树，以非传引用的方式进行传参数mm（目前最小值）和 mx（目前最大值），然后调用方法前序遍历，实际上好处就在于之前的参数不会对某个节点的左右子树的参数进行混淆...这是自己在处理本题目的时候面临的问题。

（以下是灵神的参考代码（记住啦，是灵神的！！！））

class Solution {
    int ans = 0;
    void dfs(TreeNode *node, int mn, int mx) {
        if (node == nullptr) return;
        // 虽然题目要求「不同节点」，但是相同节点的差值为 0，不会影响最大差值
        // 所以先更新 mn 和 mx，再计算差值也是可以的
        // 在这种情况下，一定满足 mn <= node.val <= mx
        mn = min(mn, node->val);
        mx = max(mx, node->val);
        ans = max(ans, max(node->val - mn, mx - node->val));
        dfs(node->left, mn, mx);//这时候传入的参数是每次进入下一个节点固有的，因此不用担心会出现混淆的情况
        dfs(node->right, mn, mx);
    }

public:
    int maxAncestorDiff(TreeNode *root) {
        dfs(root, root->val, root->val);
        return ans;
    }
};