binary-tree - 为 Leetcode 112 寻找正确的递归算法

Question

我正在解决 Leet Code 问题112。路径总和：

给定root一个二叉树和一个整数targetSum，true如果树有一个从根到叶的路径，使得沿路径的所有值相加等于 ，则返回targetSum。

叶是没有子节点的节点。

我下面的代码试图解决它，但显然它不正确，因为我不断遇到失败的测试用例。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public boolean hasPathSum(TreeNode root, int targetSum) {

        if(root.left==null&&root.right==null&&targetSum-root.val ==0)
            return true;
        else{

            if(root.right!= null){
                hasPathSum(root.right, targetSum-root.val);
            }
            if(root.left!=null) {
                hasPathSum(root.left, targetSum-root.val);
            }

        } return false;
    }
}

这段代码有什么问题？

标签： binary-treedepth-first-search

Answer 1

您没有使用您进行的递归调用返回的值。以冗长的方式，您可以按如下方式修复该部分代码：

    boolean result = false;
    if (root.right != null) {
        result = hasPathSum(root.right, targetSum - root.val);
    }
    if (!result && root.left != null) {
        result = hasPathSum(root.left, targetSum - root.val);
    }
    return result;

当您为此使用更多逻辑运算符时，它会更紧凑：

    return root.right != null && hasPathSum(root.right, targetSum - root.val)
        || root.left  != null && hasPathSum(root.left,  targetSum - root.val);

Leet Code 挑战中没有明确说明，但是当在空树上调用这个函数时，它应该返回false。所以你应该预见到 is 的root情况null。

完整的解决方案可能如下所示：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return root != null && 
            (  root.left  == null && root.right == null && targetSum == root.val
            || root.right != null && hasPathSum(root.right, targetSum - root.val)
            || root.left  != null && hasPathSum(root.left,  targetSum - root.val)
            );
    }
}