Kafka 大数据 分布式机器 Morecoin dedecms Angular class jpa encoding yii coldfusion admin框架 jquery绑定click事件 jq遍历对象 jquery延时 软件测试项目实战案例 linux管道符 python基础教程 python定义一个变量 java使用mysql java初学者 java最新框架 java当前时间 java停止线程 kafka中文教程 asp建站系统 德鲁伊武器 霜之祝福 msdev dota改键工具 一羽月土米水日古余打一成语 方正兰亭粗黑字体下载 cad自动保存位置 linux解压命令 maya骨骼绑定教程 视频抠图 win10工作组 服务器系统安装教程 c语言贪吃蛇 dnf驭剑士刷图加点
当前位置: 首页 > 学习教程  > 编程语言

力扣题解-112. 路径总和(分治法思想,递归的方式求解)

2020/12/5 9:36:52 文章标签:

题目:112. 路径总和 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum 22&#xff…

题目:112. 路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

  1. divide
    将原始二叉树分为左子树和右子树。

  2. conquer
    原问题的解hasPathSum(root, sum)分为左子树的解 hasPathSum(left, sum - root->val) 和右子树的解 hasPathSum(right, sum - root->val) 。

  3. combine
    将左右子树的解取逻辑或,得到原问题的解。

代码

/**
 * 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) {
            return false;
        }

        if (!root->left and !root->right) {
            return root->val == sum ? true: false;
        }

        return hasPathSum(root->left, sum - root->val) or hasPathSum(root->right, sum - root->val);
    }
};

本文链接: http://www.dtmao.cc/news_show_450026.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?