【LeetCode】二叉树路径问题深入浅出，一文吃透！

【LeetCode】二叉树路径问题总结

原文同步在：https://github.com/EricPengShuai/Interview/blob/main/algorithm/二叉树路径问题.md

0. 引言

二叉树路径问题就是解决从一个节点出发寻找某个路径或者到某一个节点，以满足题目要求。核心就是二叉树遍历问题，总的来说就是深度优先遍历（DFS）和广度优先遍历（BFS），更具体来说前者就是递归，后者就是迭代。

1. 问题分类

按照 星晴pro 大佬的整理，路径问题大致可以分为两类：

1.1 自顶向下

从某一个节点（不一定是根节点），从上向下寻找路径，到某一个节点（不一定是叶节点）结束，解决此类问题往往使用 DFS 和 BFS，一般来说 DFS 代码更加简洁。

DFS 模板

vector<vector<int>> res;
void dfs(TreeNode* root, vector<int> path) {
    if (!root) {
        return;
    }
    // 加入节点
    path.push_back(root->val);
    if (!root->left && !root->right) {
        res.push_back(path);
        return;
    }
    // 继续递归
    dfs(root->left, path);
    dfs(root->right, path);
}

// 指定路径和
void dfs(TreeNode* root, int sum, vector<int> path) {
    if (!root) {
        return;
    }
    // 处理节点
    sum -= root->val;
    path.push_back(root->val);
    if (!root->left && !root->right && sum == 0) {
        res.push_back(path);
        return;
    }
    // 继续递归
    dfs(root->left, sum, path);
    dfs(root->right, sum, path);
}

这类题型DFS注意点：

1. 如果是找路径和等于给定 target 的路径的，那么可以不用新增一个临时变量cursum来判断当前路径和，只需要用给定和 target 减去节点值，最终结束条件判断 target==0 即可

2. 是否要回溯：二叉树的问题大部分是不需要回溯的，原因如下：二叉树的递归部分：dfs(root->left),dfs(root->right)已经把可能的路径穷尽了，因此到任意叶节点的路径只可能有一条，绝对不可能出现另外的路径也到这个满足条件的叶节点的

   而对比二维数组(例如迷宫问题)的 DFS，for循环向四个方向查找每次只能朝向一个方向，并没有穷尽路径，因此某一个满足条件的点可能是有多条路径到该点的，并且visited数组标记已经走过的路径是会受到另外路径是否访问的影响，这时候必须回溯

3. 找到路径后是否要return：取决于题目是否要求找到叶节点满足条件的路径，如果必须到叶节点，那么就要return; 但如果是到任意节点都可以，那么必不能return,因为这条路径下面还可能有更深的路径满足条件，还要在此基础上继续递归

4. 是否要双重递归（即调用根节点的dfs函数后，继续调用根左右节点的pathsum函数）：看题目要不要求从根节点开始的，还是从任意节点开始

BFS 模板

vector<vector<int>> bfs(TreeNode* root) {
    vector<vector<int>> res;
    // 维护两个队列：节点队列和数组队列
    queue<TreeNode*> qu_node;
    queue<vector<int>> qu_path;
    if (!root) {
        return {};
    }
    qu_node.push(root);
    qu_path.push({root->val});
    
    while(!qu_node.empty()) {
        TreeNode* node = qu_node.front();
        vector<int> path = qu_path.front();
        qu_node.pop();
        qu_path.pop();
        
        if (!node->left && !node->right) {
            res.push_back(path);
        } else {
            // 注意这里需要一个副本，为了左右子树都使用这个 path
            vector<int> tmp = path;

            if (node->left != nullptr) {
                qu_node.push(node->left);
                tmp.push_back(node->left->val);
                qu_path.push(tmp);
            }
            if (node->right != nullptr) {
                qu_node.push(node->right);
                tmp.push_back(node->right->val);
                qu_path.push(tmp);
            }
        }
    }
    return res;
};

力扣中类似题目整理如下：

题目	说明	题解
257. 二叉树的所有路径	BFS代码比较复杂，DFS简练	解
面试题 04.12. 求和路径	没有要求起点和终点，需要使用双重DFS	解
112. 路径总和	简单DFS	解
113. 路径总和 II	BFS 挺好理解的，DFS 模板不需要回溯但不能用引用	解
437. 路径总和 III	双重DFS	解
988. 从叶结点开始的最小字符串	DFS 不能引用传参	解

1.2 非自顶向下

设计一个辅助函数 maxpath，调用自身求出以一个节点为根节点的左侧最长路径 left 和右侧最长路径right，那么经过该节点的最长路径就是 left+right
接着只需要从根节点开始dfs,不断比较更新全局变量即可

int res = 0;
int maxPath(TreeNode *root) // 以root为路径起始点的最长路径
{
    if (!root)
        return 0;
    int left = maxPath(root->left);
    int right = maxPath(root->right);
    res = max(res, left + right + root->val); // 更新全局变量  
    return max(left, right);   // 返回左右路径较长者
}

这类题型DFS注意点：

1. left，right 代表的含义要根据题目所求设置，比如最长路径、最大路径和等等
2. 全局变量 res 的初值设置是 0 还是 INT_MIN 要看题目节点是否存在负值，如果存在就用 INT_MIN，否则就是 0
3. 注意两点之间路径为1，因此一个点是不能构成路径的

力扣中类似题目整理如下：

题目	说明	题解
124. 二叉树中的最大路径和	内部最大路径要包含当前子树的根节点，外部返回结果只能选择一个分支的最大值返回	解
687. 最长同值路径	DFS 返回的值就是左右子树同值路径中最大的	解
543. 二叉树的直径	不能直接判断根节点是否为空，因为单个节点提供的路径也为0，当然也可以理解成高度问题	解1 解2

2. 总结

二叉树的所有遍历问题无非就是 DFS 和 BFS，DFS 代码简单但是递归理解起来有些许复杂，写递归不能自己陷到递归栈里面去，需要仔细分析题意，搞清楚递归的三步走策略：

1. 知道递归出口是什么，一般而言有如：root == nullptr
2. 明白递归的时候做什么，也就是处理左右子树时需要怎样维护我们需要的结果
3. 明确递归的返回值是什么，也就是对 DFS 而言的返回值，一般而言就是贡献给父节点的中间结果

3. 参考

• 一篇文章解决所有二叉树路径问题（问题分析+分类模板+题目剖析）