专栏首页算法工程师之路递归遍历-LeetCode 124、112、113(递归遍历二叉树,回溯法)

递归遍历-LeetCode 124、112、113(递归遍历二叉树,回溯法)

【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/

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树问题(三)-LeetCode 669、951、662、199、538、236(中序,层次遍历)

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果...

    算法工程师之路
  • 二叉树问题(四)-LeetCode 502、543、637、606、114、979(最大堆,IPO)

    假设 力扣(LeetCode)即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司,力扣 希望在 IPO 之前开展一些项目以增加其资本。由于资源有限,它只...

    算法工程师之路
  • 二叉树构建与遍历-LeetCode 103、108、109(二叉树的构建,层次遍历)

    这道题目依然是层次遍历的应用,与剑指Offer中的"之字形打印二叉树"是一样的,根据层次遍历的思路,可以将每一层压入到数组中,当层数为奇数的话,从而将该层的数据...

    算法工程师之路
  • LeetCode 965. Univalued Binary Tree

    A binary tree is univalued if every node in the tree has the same value.

    Angel_Kitty
  • LeetCode 669 Trim a Binary Search Tree

    给定二叉搜索树以及 L和 R 最低和最高边界作为修剪树,使其所有元素都在[L, R](R> = L). 您可能需要更改树的根,因此结果应返回修剪后的二叉搜索树的...

    一份执着✘
  • LintCode-632. 二叉树的最大节点

    悠扬前奏
  • Leetcode 114 Flatten Binary Tree to Linked List

    Given a binary tree, flatten it to a linked list in-place. For example, Given...

    triplebee
  • 天天算法 LeetCode-938-二叉搜索树的范围和

    https://leetcode-cn.com/problems/range-sum-of-bst/

    灵魂画师牧码
  • Sum Root to Leaf Numbers

    问题:根节点到叶子结点的所有权值和 分析:从根节点遍历,若遍历到叶子结点,则sum+其路径的所有权值和 /** * Definition for binary...

    用户1624346
  • leetcode226——翻转二叉树

    故事尾音

扫码关注云+社区

领取腾讯云代金券