二叉树 – 路径问题

针对二叉树的路径问题，似乎很难找到一个比较通用的办法。

偶然在刷leetcode的最大路径的题解中找到“星晴pro”兄弟发表的有关二叉树路径问题的思考，在此处转载一下。

“星晴Pro”兄弟将二叉树路径问题分为两类：

• 自顶向下（从某一节点从上到下寻找路径）
• 非自顶向下（从任意节点到任意节点的路径）

1 自顶向下

1.1 模版

一般路径

给定和路径

1.2 真题演练

1.2.1 面试题 04.12. 求和路径

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

class Solution {
public:
    int result = 0;
    void getPath(TreeNode* root, int sum){
        if (root==nullptr) return ;
        sum -= root->val;
        if (sum==0){ // 1 不要求叶子节点 
            result++; // 2 不要return，之后可能还有符合要求的路径
        }
        getPath(root->left, sum);
        getPath(root->right, sum);
    }

    int pathSum(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        getPath(root, sum);
        if (root->left) pathSum(root->left, sum);
        if (root->right) pathSum(root->right, sum);
        return result;
    }
};

1.2.2 112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

class Solution {
public:
    int flag = 0;
    void dfs(TreeNode* root, int targetSum){
        if (root==nullptr) return ;
        targetSum -= root->val;
        if (root->left == nullptr && root->right==nullptr && targetSum==0){
            flag = 1;
            return ;
        }
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        dfs(root, targetSum);
        if (flag) return true;
        else return false;
    }
};

1.2.3 113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

class Solution {
public:
    vector<vector> result;
    void dfs(TreeNode* root, int targetSum, vector path){
        if (root==nullptr) return ;
        targetSum -= root->val;
        path.push_back(root->val);
        if (!root->left && !root->right && targetSum==0){
            result.push_back(path);
            return ;
        }
        dfs(root->left, targetSum, path);
        dfs(root->right, targetSum, path);
    }
    vector<vector> pathSum(TreeNode* root, int targetSum) {
        vector path;
        dfs(root, targetSum, path);
        return result;
    }
};

1.2.4 437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
public:
    int result = 0;
    void dfs(TreeNode* root, int targetSum){
        if (root==nullptr) return ;
        targetSum -= root->val;
        // 1 不需要根节点才判断 
        // 2 不用return，因为可能下面还有符合要求的路径
        if (targetSum==0) result++;
        dfs(root->left, targetSum);
        dfs(root->right, targetSum);
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (root==nullptr) return 0;
        dfs(root, targetSum);
        // 将路径的起始节点切换为根结点的左节点
        pathSum(root->left, targetSum);
        pathSum(root->right, targetSum);
        return result;
    }
};

1.2.5 988. 从叶结点开始的最小字符串

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。

返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

注：字符串中任何较短的前缀在 字典序上 都是 较小 的：

• 例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。

节点的叶节点是没有子节点的节点。

class Solution {
public:
    vector result;
    void dfs(TreeNode* root, string path){
        if (root==nullptr) return ;
        path += 'a' + root->val;
        if (!root->left && !root->right){
            reverse(path.begin(), path.end());
            result.push_back(path);
            return ;
        }
        dfs(root->left, path);
        dfs(root->right, path);
    }
    string smallestFromLeaf(TreeNode* root) {
        if (root == nullptr) return "";
        string path = "";
        dfs(root, path);
        sort(result.begin(), result.end());
        return result[0];
    }
};

2 非自顶向下

2.1 模版

2.2 真题演练

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

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

class Solution {
public:
    int res = INT_MIN;
    int maxPath(TreeNode* root){
        if (root == nullptr) 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(left+root->val, right+root->val);
    }

    int maxPathSum(TreeNode* root) {
        maxPath(root);
        return res;
    }
};

2.2.2 687. 最长同值路径

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

class Solution {
public:
    int result = 0;
    int dfs(TreeNode* root){
        if (root == nullptr) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if (root->left && root->left->val == root->val) left++;
        else left = 0;
        if (root->right && root->right->val == root->val) right++;
        else right = 0;
        result = max(result, left+right);
        return  max(left, right);
    }

    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return result;
    }
};

2.2.3 543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

class Solution {
public:
    int result = 0;
    int dfs(TreeNode* root){
        if (root==nullptr) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if (root->left) left++;
        if (root->right) right++;
        result = max(result, left+right);
        return max(left, right);
    }

    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return result;
    }
};