递归遍历-LeetCode 124、112、113（递归遍历二叉树，回溯法）

算法工程师之路

发布于 2019-11-04 02:32:17

8750

发布于 2019-11-04 02:32:17

文章被收录于专栏：算法工程师之路算法工程师之路

【LeetCode #124 二叉树的最大路径和】

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3] 1 / \ 2 3 输出: 6

解题思路：

我们从根节点开始递归，最大值的路径和可能出现在左子树，右子树以及包含根节点的左右子树三种情况。因此使用递归算法从根节点开始遍历，如果左右子树最大路径和大于0，则取出该路径的最大值，否则为零，也就是说如果大于零，则加上之后result是可以增加的！因此对result进行更新，同时递归函数也返回root->val + max(0, max(left, right))。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int result;


    int dfs(TreeNode* root){
        if(!root)  return 0;
        int left = max(dfs(root->left), 0);
        int right = max(dfs(root->right), 0);
        result = max(root->val+left+right, result);
        return root->val + max(0, max(left, right));
    }

    int maxPathSum(TreeNode* root) {
        if(!root)  return 0;
        result = root->val;
        dfs(root);
        return result;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

【LeetCode #112】路径总和

解题思路：

这是一个分治思路，求一个二叉树中存不存在某一个路径和为sum，可以变换问题为：

对于一个节点root, 如果其左子树存在，则其左子树存不存在一个路径和为sum-root->val, 如果其右子树存在，则其右子树存不存在一个路径和为sum-root->val！如存在，返回true!
如果到达叶节点，也就是root->left以及root->right均为NULL，则其root->val等不等于sum, 如果等于则返回true.
如果root本身为空或者不满足上述条件，返回false

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        if (root->left == NULL && root->right == NULL && root->val == sum) return true;
        if (root->left != NULL && hasPathSum(root->left, sum - (root->val))) return true;
        if (root->right != NULL && hasPathSum(root->right, sum - (root->val))) return true;
        return false;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/path-sum

【LeetCode #113】路径总和II

解题思路：

和上一题的思路一模一样，但这一题需要我们将中间遍历的节点值保存起来，因此需要一个tmp数组来保存我们遍历过的节点！这里面需要注意的一点就是回溯法的使用，当修改了一个状态之后，递归结束后，需要把这个状态重新置为之前的状态。 比如tmp中push_back了一个值，当递归结束进行回溯阶段，需要pop_back()。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res; vector<int> tmp;

    void dfs(TreeNode* root, int sum){
        tmp.push_back(root->val);   // 修改状态
        if(root->left == NULL && root->right == NULL && sum == root->val){
            res.push_back(tmp);
            return;
        }
        if(root->left != NULL){

            dfs(root->left,  sum-root->val);
            tmp.pop_back();    // 回溯
        }
        if(root->right != NULL){

            dfs(root->right,  sum-root->val);
            tmp.pop_back();   // 回溯
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(root == NULL) return res;
        dfs(root, sum);
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/path-sum-ii/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-10-29，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树