你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

二叉树路径问题系列(问题分析+分类模板+题目剖析)c++

2021-11-13 21:47:54

参考链接:https://leetcode-cn.com/problems/paths-with-sum-lcci/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-w3hu/

问题分类

二叉树路径的问题大致可以分为两类:
1、自顶向下:
顾名思义,就是从某一个节点(不一定是根节点),从上向下寻找路径,到某一个节点(不一定是叶节点)结束
具体题目如下:
257. 二叉树的所有路径
面试题 04.12. 求和路径
112. 路径总和
113. 路径总和 II
437. 路径总和 III
988. 从叶结点开始的最小字符串

而继续细分的话还可以分成一般路径与给定和的路径

2、非自顶向下:
就是从任意节点到任意节点的路径,不需要自顶向下
124. 二叉树中的最大路径和
687. 最长同值路径
543. 二叉树的直径

解题模板

这类题通常用深度优先搜索(DFS)和广度优先搜索(BFS)解决,BFS较DFS繁琐,这里为了简洁只展现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);
}

二、非自顶而下:

这类题目一般解题思路如下:
设计一个辅助函数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);   //返回左右路径较长者
}

在这里插入图片描述
在这里插入图片描述

/**
 * 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:
    vector<string>res;
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root,"");
        return res;
    }
    void dfs(TreeNode*root,string path){
        if(!root){
            return ;
        }
        path += to_string(root->val);//把根节点加入路径
        if(!root->left && !root->right){//到达叶节点
            res.push_back(path);//路径加入结果中
            return;
        }
        dfs(root->left,path+"->");//继续遍历
        dfs(root->right,path+"->");
    }
};

在这里插入图片描述
在这里插入图片描述在这里插入图片描述

/**
 * 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:
    vector<vector<int>>res;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int>path;
        dfs(root,targetSum,path);
        return res;
    }
    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);

    }
};

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

/**
 * 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 count;
    int pathSum(TreeNode* root, int targetSum) {
        if(!root){
            return 0;
        }
        dfs(root,targetSum); //以root为起始点查找路径
        pathSum(root->left,targetSum);//左子树递归
        pathSum(root->right,targetSum);//右子树递归
        return count;
    }
    void dfs(TreeNode* root,int sum){
        if(!root){
            return;
        }
        sum -= root->val;
        if(sum == 0){//注意不要return,因为不要求到叶节点结束,所以一条路径下面还可能有另一条
            count++;//如果找到了一个路径全局变量就+1
        }
        dfs(root->left,sum);
        dfs(root->right,sum);
    }
};

在这里插入图片描述
在这里插入图片描述

/**
 * 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:
    vector<string>res;
    string smallestFromLeaf(TreeNode* root) {
        dfs(root,"");
        sort(res.begin(),res.end());//升序排列
        return res[0];//返回第一个路径
    }
    void dfs(TreeNode* root,string path){
        if(!root){
            return ;
        }
        path += 'a'+root->val;//0:a,加上a就等于转换字母
        if(!root->left && !root->right){
            reverse(path.begin(),path.end());//从叶节点到根节点
            res.push_back(path);
            return;
        } 
        dfs(root->left,path);
        dfs(root->right,path);
    }
};

二、非自顶向下

在这里插入图片描述
在这里插入图片描述

/**
 * 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 res = INT_MIN; //注意节点值可能为负数,因此要设置为最小值
    int maxPathSum(TreeNode* root) {
        maxPath(root);
        return res;

    }
    // left,right分别为根节点左右子树最大路径和,注意:如果最大路径和<0,意味着该路径和对总路径和做负贡献,因此不要计入到总路径中,将它设置为0
    int maxPath(TreeNode* root){ //以root为路径起始点的最长路径
        if(!root){
            return 0;
        }
        int left = max(maxPath(root->left),0);
        int right = max(maxPath(root->right),0);
        res = max(res,left+right+root->val);//比较当前最大路径和与左右子树最长路径加上根节点值的较大值,更新全局变量
        return max(root->val+left,root->val+right);
    }
};
  1. 最长同值路径
    在这里插入图片描述在这里插入图片描述
/**
 * 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 res;
    int longestUnivaluePath(TreeNode* root) {
        longestPath(root);
        return res;

    }
    int longestPath(TreeNode* root){
        if(!root){
            return 0;
        }
        int left = longestPath(root->left);
        int right = longestPath(root->right);
        // 如果存在左子节点和根节点同值,更新左最长路径;否则左最长路径为0
        if(root->left && root->val == root->left->val){
            left++;
        }else{
            left = 0;
        }
        if(root->right && root->val == root->right->val){
            right++;
        }else{
            right = 0;
        }
        res = max(res,left+right);
        return max(left,right);

    }
};
  1. 二叉树的直径
    在这里插入图片描述
/**
 * 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 res;
    int diameterOfBinaryTree(TreeNode* root) {
        maxPath(root);
        return res;
    }
    int maxPath(TreeNode* root){
        if(!root){
            return 0;
        }
        int left = maxPath(root->left);
        int right = maxPath(root->right);
        if(root->left){
            left++;
        }
        if(root->right){
            right++;
        }
        res = max(left+right,res);
        return max(left,right);
    }
};