题解 | #二叉树中和为某一值的路径(一)#

二叉树中和为某一值的路径(一)

http://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c

采用二叉树的先序遍历,在叶子结点判断数字和是否相等即可,需要注意的是测试数据里,如果根结点的值等于数字和,是不算一条路径的,所以需要进行排除;而且题目只要求找到一条路径,所以可以假如左子树已经找到路径,那么右子树就不需要找了,可以进行剪枝。

时间复杂度最慢O(N),平均复杂度小于O(N)

空间复杂度O(1)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        return root == null || root.val == sum && (root.left != null || root.right != null)? false : preTravelTree(root, sum, 0);
    }
    
    public boolean preTravelTree(TreeNode t, int sum, int count){
        if(t == null)
            return sum == count;
        count += t.val;
        return preTravelTree(t.left, sum, count) ? true : preTravelTree(t.right, sum, count);
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 13:15
点赞 评论 收藏
分享
06-20 19:40
中原工学院 Java
网络存储:十几天不会让你拉人办卡就结束了吧?
点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 12:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务