精华内容
下载资源
问答
  • LeetCode二叉树路径和

    2020-02-05 16:44:25
    找出路径和等于给定数值的路径总数。 路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] ...

    记录第一篇博客,养成好习惯

    题目描述

    给定一个二叉树,它的每个结点都存放着一个整数值。

    找出路径和等于给定数值的路径总数。

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

    二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。

    示例:

    root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

    10
    /
    5 -3
    / \
    3 2 11
    / \
    3 -2 1

    返回 3。和等于 8 的路径有:

    1. 5 -> 3
    2. 5 -> 2 -> 1
    3. -3 -> 11

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

    题解

    思路

    1.在题干的描述中难点在于路径不需要从根节点开始,也不需要在叶子节点结束

    1)不妨先考虑路径必须要从根节点开始再到叶节点结束,记录路径中满足sum的路径和,这就会构成第一层递归

    此时遍历在叶节点结束,但构成sum的路径不一定结束在叶节点

    2)将每个遍历到的节点都看作根节点,则构成第二层递归

    此时每个遍历到的节点,则会实现不一定从根节点出发

    代码(Python实现)

    class Solution(object):
    
        #第一层递归,类似于树的中序遍历
        #实现:让遍历到的每个节点,依次作为根节点
        def pathSum(self, root, sum):
            pathNum=0
            if root!=None and root.val!=None:
                pathNum=pathNum+self.fun(root,sum)
                pathNum=pathNum+self.pathSum(root.left,sum)
                pathNum=pathNum+self.pathSum(root.right,sum)
            return pathNum
    
    
        #第二层递归
        #实现:找出从root节点出发到叶节点过程中,和为tempSum的路径总和
        #(注意此处的tempSum与题干中要求的sum并不相同)
        def fun(self,root,tempSum):
            pathNum=0
            if root!=None:
                tempSum=tempSum-root.val
                if tempSum==0:
                    #此时可能还未到达叶节点
                    pathNum=pathNum+1
                    
                pathNum=pathNum+
                	self.fun(root.left,tempSum)+
                	self.fun(root.right,tempSum)
            return pathNum
    
    展开全文
  • 这道二叉树路径在之前的基础上又需要找出路径 ,但是基本思想都一样,还是需要用深度优先搜索DFS,只不过数据结构相对复杂一点,需要用到二维的vector,而且每当DFS搜索到新节点时,都要保存该节点。而且每当找...

    1.

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

    For example:
    Given the below binary tree and sum = 22,

     

                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1
    
    /**
      * Definition for binary tree
      * struct TreeNode {
      *     int val;
      *     TreeNode *left;
      *     TreeNode *right;
      *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      * };
      */
     class Solution {
     public:
         bool dfs(TreeNode *node, int sum, int curSum)
         {
             if (node == NULL)
                 return false;
             
             if (node->left == NULL && node->right == NULL)
                 return curSum + node->val == sum;
                    
             return dfs(node->left, sum, curSum + node->val) || dfs(node->right, sum, curSum + node->val);
         }
         
         bool hasPathSum(TreeNode *root, int sum) {
             
             return dfs(root, sum, 0);
         }
     };
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
      * };
     */
    bool dfs(struct TreeNode *node, int sum, int cur);
    bool hasPathSum(struct TreeNode *root, int sum) {
        return dfs(root, sum, 0);
    }
    
    bool dfs(struct TreeNode *node, int sum, int cur){
        if(node == NULL) return false;
        if(node->left == NULL && node->right == NULL)
            return cur+node->val == sum;
        return(dfs(node->left, sum, cur+node->val) || dfs(node->right, sum, cur+node->val));
    }

    2.路径和,打印路径

    Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

    For example:
    Given the below binary tree and sum = 22,

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

    return

    [
       [5,4,11,2],
       [5,8,4,5]
    ]
    
    这道二叉树路径之和在之前的基础上又需要找出路径 ,但是基本思想都一样,还是需要用深度优先搜索DFS,只不过数据结构相对复杂一点,需要用到二维的vector,而且每当DFS搜索到新节点时,都要保存该节点。而且每当找出一条路径之后,都将这个保存为一维vector的路径保存到最终结果二位vector中。并且,每当DFS搜索到子节点,发现不是路径和时,返回上一个结点时,需要把该节点从一维vector中移除。代码如下:
    class Solution {
    public:
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            vector<vector<int>> res;
            vector<int> out;
            helper(root, sum, out, res);
            return res;
        }
        void helper(TreeNode* node, int sum, vector<int>& out, vector<vector<int>>& res) {
            if (!node) return;
            out.push_back(node->val);
            if (sum == node->val && !node->left && !node->right) {
                res.push_back(out);
            }
            helper(node->left, sum - node->val, out, res);
            helper(node->right, sum - node->val, out, res);
            out.pop_back();
        }
    };

    3.没必要从开始到叶子节点结束,任意路径和。

    You are given a binary tree in which each node contains an integer value.

    Find the number of paths that sum to a given value.

    The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

    The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

    Example:

    root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    Return 3. The paths that sum to 8 are:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3. -3 -> 11

    这道题让我们求二叉树的路径的和等于一个给定值,说明了这条路径不必要从根节点开始,可以是中间的任意一段,而且二叉树的节点值也是有正有负。那么我们可以用递归来做,相当于先序遍历二叉树,对于每一个节点都有记录了一条从根节点到当前节点到路径,同时用一个变量curSum记录路径节点总和,然后我们看curSum和sum是否相等,相等的话结果res加1,不等的话我们来继续查看子路径和有没有满足题意的,做法就是每次去掉一个节点,看路径和是否等于给定值,注意最后必须留一个节点,不能全去掉了,因为如果全去掉了,路径之和为0,而如果假如给定值刚好为0的话就会有问题,整体来说不算一道很难的题,参见代码如下:

    class Solution {
    public:
        int pathSum(TreeNode* root, int sum) {
            int res = 0;
            vector<TreeNode*> out;
            helper(root, sum, 0, out, res);
            return res;
        }
        void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>& out, int& res) {
            if (!node) return;
            curSum += node->val;
            out.push_back(node);
            if (curSum == sum) ++res;
            int t = curSum;
            for (int i = 0; i < out.size() - 1; ++i) {
                t -= out[i]->val;
                if (t == sum) ++res;
            }
            helper(node->left, sum, curSum, out, res);
            helper(node->right, sum, curSum, out, res);
            out.pop_back();
        }
    };

     

    展开全文
  • Path Sum 1、题目 fen

    Path Sum

    1、题目

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

    For example:
    Given the below binary tree and  sum = 22 ,
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1
    

    return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.


    2、分析

    这道题很简单,用递归
    代码一目了然

    3、代码

    /**
     * Definition for binary tree
     * 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;         //空树,返回false   
            if(!root->left && !root->right)  return root->val==sum;      //左右子树均为空,判断val是否等于sum
            return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);    //递归调用hasPathSum函数
        }
    };


    Path Sum II

    1、题目

    Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

    For example:
    Given the below binary tree and  sum = 22 ,
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    

    return

    [
       [5,4,11,2],
       [5,8,4,5]
    ]

    2、分析


    递归法,对递归函数执行的逻辑要理清,画图模拟一遍有帮助于理解程序的执行流程

    3、代码

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            vector< vector<int> > result;
            vector<int> current;
            pathSum(root,sum,current,result);
            return result;
        }
    private:
        void pathSum(TreeNode *root,int sum,vector<int> current,vector<vector<int>> &result)
        //必须用引用&,否则传递过来的只是current、result的副本,函数递归调用结束后,这些副本在栈里面被释放掉,并未真正改变current、result
        {
            if(!root)  return;
            
            current.push_back(root->val);
            if(!root->left && !root->right)  
            {
                if(sum==root->val)   
                  result.push_back(current);
            }
            
            pathSum(root->left,sum-root->val,current,result);
            pathSum(root->right,sum-root->val,current,result);
            
           current.pop_back();     //pop掉容器最后一个元素
        }
    };


    展开全文
  • Leetcode 二叉树路径

    2020-05-28 10:53:07
    给定一个二叉树和一个值sum,判断是否有从根节点到叶子节点的节点值之等于sum的路径, 例如: 给出如下的二叉树,sum=22, 5↵ / ↵ 4 8↵ / / ↵ 11 13 4↵ / / ↵ 7 2 5 1 返回true,因为存在一条路径5-&...

    题目描述

    给定一个二叉树和一个值sum,判断是否有从根节点到叶子节点的节点值之和等于sum的路径,

    例如:

    给出如下的二叉树,sum=22,

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

    返回true,因为存在一条路径5->4->11->2的节点值之和为22

     

    思路:DFS  当到达叶子节点时,判断是否等于sum  是就及时返回   不是继续搜索

    bool hasPathSum(TreeNode* root, int sum) {
            // write code here
            if(root==NULL)
            {
                
                    return false;
            }
            if(root->left==NULL && root->right==NULL) //到达叶子节点
            {
                if(root->val==sum)
                    return true;
                else
                    return false;
            }
            if(root->left!=NULL)
            {
                if(hasPathSum(root->left,sum-root->val))  //左子树有满足条件的
                    return true;
            }
            if(root->right!=NULL)
            {
                if(hasPathSum(root->right,sum-root->val))
                    return true;
            }
            return false;//都没有找到
            
            
            
        }

    进一步:返回所有的满足sum的路径

    思路:同样采用DFS遍历  若满足 存入全局的res答案中

     vector<vector<int>> res;
        
        vector<vector<int> > pathSum(TreeNode* root, int sum) {
            // write code here
            
            vector<int> path;
            DFS(root,sum,path);
            return res;
            
        }
        
        void DFS(TreeNode* root,int sum,vector<int> path)
        {
            if(root==NULL)
                return;
            path.push_back(root->val);//路径加入当前节点
            if(root->left==NULL && root->right==NULL) //到达根节点
            {
                if(sum==root->val)//满足
                {
                    res.push_back(path);//存入答案中
                    
                }
            }
          DFS(root->left,sum-root->val,path);
          DFS(root->right,sum-root->val,path);
           
            
        }
        

     

     

    展开全文
  • /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func hasPathSum(root *TreeNode, targetSum int) bool { if nil == root { ...
  • class Solution: def sumNumbers(self, root: TreeNode) -> int: if not root: return 0 self.res = 0 def dfs(node,recode): if not node.left and not node.right: self.res += (recode*10 + node.val) ...
  • (尊重劳动成果,转载请...题目大意是这个意思,给定一棵二叉树和一个sum值,判断树中是否存在一条从根节点到叶子节点的路径,使得路径上的值加起来刚好等于sum。 解题思路: 递归结束条件: root == null返回fal...
  • class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root == null) return false; if(root.left == null &... root.right =... return targetSum - root.val &#...
  • 给定一个二叉树和一个目标,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标。 示例: 给定如下二叉树,以及目标 sum = 22, 5 / \ 4 8 / / \ 11 13 4 ...
  • 给定一个二叉树和一个目标,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标 sum = 22, 5 / \ 4...
  • leetcode:二叉树路径和

    2020-03-26 12:45:43
    注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。 审题: 题目中的重点包括如下: 节点值或正或负 路径可从任意节点开始 路径只能沿父节点到子节点 ...
  • //二叉树输出路径 vector < string > TreePaths; void DFS(binaryTreeNode* node, string answer) { answer += "->" + to_string(node->m_nValue); if (node->m_pLeft == NULL && node->m_pRight == ...
  • leetcode144 二叉树的前序遍历2. leetcode94 二叉树的中序遍历3. leetcode145 二叉树的后序遍历4. leetcode102 二叉树的层序遍历5. leetcode107 二叉树的层序遍历II6. leetcode104 二叉树的最大深度7. leetcode543 ...
  • LeetCode 二叉树中的最大路径和

    千次阅读 2019-02-21 20:44:09
    给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 6 示例 2: ...
  • 主要思想,递归遍历整棵二叉树,每遍历到一个节点,并把节点加入路径,判断是否为叶节点 1.是叶节点,就把当前这个路径添加到List里, 2.不是叶节点,就在当前路径后加“->”(这是因为题目有格式要求,如果没有...
  • 给定一个二叉树,请计算节点值之最大的路径的节点值之和是多少。 这个路径的开始节点结束节点可以是二叉树中的任意节点 例如: 给出以下的二叉树, 1↵ / ↵ 2 3 返回的结果为6 思路:最长连续子...
  • 思路 一开始没有什么思路,看了大家的评论之后大概了解了可以用递归算的方法,最关键的就是有一个变量sum记录最大路径(加上...max_left,max_right标记新的根结点加上以被选择的最长的左子树右子树的路径,left_ga...
  • leetcode 二叉树题目总结一.基本问题遍历前序遍历后序遍历中序遍历莫里斯遍历:空间复杂度O(1)层次遍历由序列构造二叉树递归解决二叉树问题:将二叉树转换为其他结构 二叉树结构: struct TreeNode { int val; ...
  • LeetCode 二叉树的直径

    2020-12-22 05:06:45
    一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意:两结点之间的路径长度是...
  • LeetCode 二叉树递归方法1.二叉树介绍1.1 二叉树含义1.2 二叉树遍历方法2. 二叉树的递归方法2.1 递归三要素2.2 递归实现二叉树遍历3.案例分析3.1 二叉树的最大深度参考资料 1.二叉树介绍 1.1 二叉树含义 树 是一种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,470
精华内容 6,188
关键字:

leetcode二叉树路径和