二叉树中最大祖先差值

"这篇文档是关于C++实现的LeetCode问题——寻找二叉树中节点与祖先的最大差值。" 在二叉树中，给定一个根节点`root`，我们需要找到两个不同的节点`A`和`B`，使得它们之间的差值`|A.val - B.val|`最大，同时`A`是`B`的祖先。这个问题可以通过两种DFS（深度优先搜索）方法来解决。 方法一：两重DFS 这种方法首先遍历所有的节点，对于每个节点，再进行一次DFS来遍历它的所有后代。在遍历过程中，可以记录下当前节点到祖先节点的差值，并与已知的最大差值进行比较，更新结果。由于每个节点可能会成为多个后代节点的祖先，所以这种方法需要对所有可能的祖先-后代组合进行检查。 ```cpp void dfs1(TreeNode* node, int parentVal) { // ... for (child : children of node) { dfs1(child, node->val); } // ... } ``` 方法二：一重DFS，最值法 这个方法只需要一次DFS，通过一个函数来跟踪到达当前节点的最大值和最小值。在回溯过程中，计算当前节点与父节点的差值，并更新最大差值。由于我们无法确定当前节点的子节点何时会成为祖先，因此我们需要两个变量分别记录路径上的最大值和最小值。 ```cpp int dfs2(TreeNode* node, int maxValue, int minValue) { // ... maxValue = max(maxValue, node->val); minValue = min(minValue, node->val); if (node->left) dfs2(node->left, maxValue, minValue); if (node->right) dfs2(node->right, maxValue, minValue); // ... } ``` 在二叉树节点的定义中： ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ``` 在`Solution`类中，可以定义这两个DFS函数，并在主函数中调用它们，比较其结果并返回最大差值。 ```cpp class Solution { public: int maxAncestorDiff(TreeNode* root) { // 调用DFS方法，初始化最大差值为0 return dfs2(root, root->val, root->val); } private: int dfs2(TreeNode* node, int maxValue, int minValue) { // ... } }; ``` 这个问题的关键在于有效地利用DFS来遍历所有可能的祖先-后代路径，并在回溯过程中更新最大差值。这两种方法都是通过递归地遍历二叉树结构来解决问题的，但方法二通过减少递归层次提高了效率。在实际应用中，应该根据具体问题的复杂性和性能要求选择合适的方法。