LeetCode437：二叉树路径和求解
LeetCode437给定一个二叉树的根节点root和一个整数targetSum求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。示例输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8输出3Python解法DFSclass Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) - int: # 内层函数以当前node为起点统计向下凑够remain_sum的路径数量 def rootSum(node, remain_sum): if node is None: return 0 valid_cnt 0 # 当前节点值等于剩余需要凑的和找到一条合法路径 if node.val remain_sum: valid_cnt 1 # 递归左右子树剩余目标和减去当前节点值 valid_cnt rootSum(node.left, remain_sum - node.val) valid_cnt rootSum(node.right, remain_sum - node.val) return valid_cnt if root is None: return 0 total_cnt rootSum(root, targetSum) total_cnt self.pathSum(root.left, targetSum) total_cnt self.pathSum(root.right, targetSum) return total_cntJava解法DFSclass Solution { public int pathSum(TreeNode root, int targetSum) { if (root null) return 0; // 当前节点作为起点的路径数 左子树全部起点 右子树全部起点 int totalCnt rootSum(root, targetSum); totalCnt pathSum(root.left, targetSum); totalCnt pathSum(root.right, targetSum); return totalCnt; } // 以 node 为起点向下统计剩余需要凑 remainSum 的路径数量 private int rootSum(TreeNode node, int remainSum) { if (node null) return 0; int validCnt 0; if (node.val remainSum) { validCnt; } // 剩余目标和减去当前节点值递归左右 validCnt rootSum(node.left, remainSum - node.val); validCnt rootSum(node.right, remainSum - node.val); return validCnt; } }C解法DFSclass Solution { public: int pathSum(TreeNode* root, int targetSum) { if (!root) return 0; int totalCnt rootSum(root, targetSum); totalCnt pathSum(root-left, targetSum); totalCnt pathSum(root-right, targetSum); return totalCnt; } private: // node路径起点remainSum还需要凑的剩余和 int rootSum(TreeNode* node, long long remainSum) { if (!node) return 0; int validCnt 0; if (node-val remainSum) { validCnt; } validCnt rootSum(node-left, remainSum - node-val); validCnt rootSum(node-right, remainSum - node-val); return validCnt; } };
