Problem: 124. 二叉树中的最大路径和

思路

• dfs作为一种遍历方式，通常通过递归实现，其在树和图中都有应用，因此以下思路对于树和图都可以使用。
• dfs言最重要的两点是节点的操作和数据的传递。
  • 节点的操作要考虑在递归子节点的先后顺序，在前面的称为先序遍历或自顶向下，在后面的称为后序遍历或自底向上。
  • 数据的传递要考虑传递时的方向，由父节点到子节点的是自顶向下，由子节点到父节点的时自底向上。

实现

• 数据的传递方式根据方向有所不同。
  • 自顶向下一般通过函数参数，自底向上一般通过返回值。
  • 而一些更为通用的方式——引用类型的参数，仿函数的成员变量或者全局变量可以更为灵活的双向进行传递。
  • 在实际题目中可能会有多种数据需要以不同的流向在dfs中传递，这时，根据这样的划分方式可以对应的找到更好的数据传递方式，可以写出更优美的代码。
• 操作节点时，通常需要使用数据，或生成数据，或者二者皆有。而这部分数据又在dfs的过程中流动，那我们就需要考虑dfs的过程和数据流向的关系了。
  • 众所周知，dfs是先从根遍历到子节点，之后再回到根，那么根据这样一个过程，数据的流向就是从跟流到子节点，再返回根。
  • 这意味着如果某个节点操作所需要的数据来自父节点(1)，或者产生的数据要流向父节点(2)，那么这个操作可以在任意位置；然而如果操作所需要的数据来自子节点(3)，他需要进行后序遍历，如果产生的数据要流向子节点(4)，他需要进行先序遍历。
  • 通常在实际题目中，可能要对节点进行不止一个操作，这时不一定需要进行多次递归，可以将每一个操作与数据的依赖关系区分明白，区分开每个操作之间的依赖关系，如果没有矛盾，就可以合理的安排先后顺序将多次操作合并在一次递归中。让每次递归做更多的事，从而提升效率。

实例分析

int ans = -999999999;

void aux(TreeNode *t) {
    if (t == nullptr) return;
    int l = maxPath(t->left);
    int r = maxPath(t->right);
    int curr = t->val;
    if (l > 0 && r > 0) {
      curr = l + r + curr;
    } else if (l > 0) {
      curr = l + curr;
    } else if (r > 0) {
      curr = r + curr;
    }
    ans = max(ans, curr);
    aux(t->left);
    aux(t->right);
}

int maxPath(TreeNode *root) {
    if (root == nullptr) return 0;
    else return max(maxPath(root->left), maxPath(root->right)) + root->val;
}

• 例如对于本题，对于节点有两个操作分别是计算当前树从根开始的最长路径(操作一)和计算不跨越当前树的子树的最长路径(操作二)。
  • 前者需要的数据来自子节点(3)，数据要流向父节点(2)，因此需要后序遍历操作。
  • 后者需要的数据来自子节点(3)，数据要流向父节点(2)，同样需要后序遍历操作。
  • 而操作二又依赖于操作一，这说明我们的操作并不矛盾，两个操作在同一个dfs中安排成自底向上(后序遍历操作)即可。在正确答案中两份数据一个通过返回值，一个通过仿函数的成员变量向上传递，效率很高。
• 而对于上述的实现，将操作一放在了先序遍历操作中，而操作一又依赖于操作二，在实现的时候发现没办法一遍完成，就在递归中嵌套了递归。将两个操作分到两个递归并嵌套，这无疑增加了非常多的重复计算，最后的效果也可想而知。

总结

在实际题目中，我们可能遇到需要多步不同操作，操作之间有复杂的依赖关系。这时就需要我们按照以上分类，理清每个操作可能的位置，将其中冲突的拆解到不同的dfs中，不冲突的合并在一个dfs中。从而正确的实现。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if(!root) return 0;
        int res = INT_MIN;

        auto dfs = [&] (auto && dfs, TreeNode* curr) -> int {
            if(!curr) return 0;
            auto lm_path = dfs(dfs, curr->left);
            auto rm_path = dfs(dfs, curr->right);

            res = max(res, curr->val + lm_path + rm_path);

            return max(0, max(curr->val, max(lm_path, rm_path) + curr->val));
        };
        dfs(dfs, root);
        return res;
    }
};