Path Sum 二叉树 判断根节点到叶子节点之和是否有sum

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.

思想:深度搜索,当搜索到叶子节点的时候,判断sum – node.val是否是0,是的话就返回true,否的话就返回false,左右子树只要有一个返回true,就返回true
叶子节点:左孩子null,右孩子null
递归的时候,如果先看成立条件,就是 node !=null, node.left == null,  node.right ==null,sum – node.val == 0
再看不成立条件
分左孩子null 或 右孩子null,进行递归,左孩子或右孩子进行递归 还有就是 node == null ,返回false

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class PathSum {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        else
            return pathSum(root, 0, sum);

    }

    private boolean pathSum(TreeNode root, int now, int result) {
        TreeNode left = root.left;
        TreeNode right = root.right;

        if (root != null  //root不为空,左孩子空,右孩子为空,root为叶子节点
                && left == null
                && right == null
                && result == now + root.val) return true;
        else if (root != null//root不为空,右孩子空,左孩子不空,当前值now + root.value 不等于目标值result,递归判断左子树
                && root.right ==null
                && root.left != null
                && result - root.val != now)
            return pathSum(root.left,now + root.val, result);
        else if (root != null//root不为空,左孩子空,右孩子不空,当前值now + root.value 不等于目标值result,递归判断右子树
                && root.right != null
                && root.left == null
                && result - root.val != now)
            return pathSum(root.right, now + root.val, result);
        else if (root != null  //root不空,左子树不空,右子树不空,递归判断左子树和右子树,如果有一个子树返回true,也返回true
                && root.right != null
                && root.left != null
                /*&& result - root.val != now*/)
            return pathSum(root.left, now + root.val, result ) || pathSum(root.right, now + root.val, result);
        else return false;
    }

}

/*----------------------------------------
虽然上述方法清晰,但是复杂。以下与上述思想相同,但是实现很简单
*/
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;

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

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

为啥只想到了第一种方法,而且吭哧吭哧想半天,想清楚了返回条件,只想了sum – node.val == 0, 没想清楚子节点情况,想到root.left,root.right,再开始想判断root是否是null,左右节点是否是null,情况分析清楚后写的代码就过于复杂。
下次写递归算法,先写清楚条件,能合起来写的需要合起来写。

Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据