算法题练习——JS Node+python题解BM29 二叉树中和为某一值的路径

た入场券 2024-04-06 09:27 52阅读 0赞

**描述**

> 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
> 
> 1.  该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
> 2.  叶子节点是指没有子节点的节点
> 3.  路径只能从父节点到子节点，不能从子节点到父节点
> 4.  总节点数目为n

**例如：**

> 给出如下的二叉树，sum=22

![83851b6763ea4d23a13c2c39e245635f.png][]

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

**数据范围：**

> 1.树上的节点数满足 0≤n≤10000
> 
> 2.每 个节点的值都满足 ∣val∣≤1000

**要求：**

> 空间复杂度 O(n)，时间复杂度 O(n)

**进阶：**

> 空间复杂度 O(树的高度)，时间复杂度 O(n)

**示例1**

> 输入：\{5,4,8,1,11,\#,9,\#,\#,2,7\},22
> 
> 返回值：true

**示例2**

> 输入：\{1,2\},0
> 
> 返回值：false

**示例3**

> 输入：\{1,2\},3
> 
> 返回值：true

**示例4**

> 输入：\{\},0
> 
> 返回值：false

**JavaScript题解：**

/*
     * function TreeNode(x) {
     *   this.val = x;
     *   this.left = null;
     *   this.right = null;
     * }
     */
    
    /**
      * 
      * @param root TreeNode类 
      * @param sum int整型 
      * @return bool布尔型
      */
    function hasPathSum( root ,  sum ) {
        // write code here
        if(!root) return false
        if(!root.left && !root.right){
            if(sum-root.val === 0){
                return true
            }else{
                return false
            }
        }
        return hasPathSum(root.left,sum-root.val) ||hasPathSum(root.right,sum-root.val)
    }
    module.exports = {
        hasPathSum : hasPathSum
    };

**Python题解：**

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param root TreeNode类 
    # @param sum int整型 
    # @return bool布尔型
    #
    class Solution:
        def hasPathSum(self , root: TreeNode, sum: int) -> bool:
            # write code here
            if not root:
                return False
            if not root.left and not root.right and sum-root.val == 0:
                return True
            return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)

[83851b6763ea4d23a13c2c39e245635f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/e411ffc879b942c08c134d1ac198c8b9.png