leetcode 112.路径总和

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
相关话题：树、深度优先搜索    难度：简单
示例:

给定如下二叉树，以及目标和 sum = 22，

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
思路：二叉树的题一般都会想到用递归来做。递归整棵树，如果当前节点为空那就是没有到路径尽头，若没有左孩子也没有右孩子也就是说它是叶子节点，那就看sum累加到当前节点时候等于目标和了。

• 我刚开始的做法

 public boolean hasPathSum(TreeNode root, int sum) {
        int[] has = new int[1];
        hasPathSum(root, sum, has);
        return has[0]== 1?true:false;
    }
    public void hasPathSum(TreeNode root, int sum, int[] has){
        if(root == null) return;
        if(root.left == null && root.right == null && sum == root.val){
            has[0] = 1;
        }
        hasPathSum(root.left, sum - root.val, has);
        hasPathSum(root.right, sum - root.val, has);
    }

我这里的做法是root == null直接返回，root.left == null && root.right == null && sum == root.val那就看sum有没累加到目标和了。因为java值传递的缘故，还搞了个数组保存返回值。
如果不是叶子，那就递归左右子树，此时sum = sum - root.val表示已经加了root.val，子树的目标和只需要sum-root.val。

• 优雅递归

public boolean hasPathSum(TreeNode root, int sum) {
         if(root == null) return false;
         if(root.left == null && root.right == null && 
            sum == root.val)
             return true;
         return hasPathSum(root.left,sum - root.val) || 
                      hasPathSum(root.right,sum - root.val);
    }

递归二叉树，若root == null直接返回false,若root.left == null && root.right == null && sum == root.val表示到了叶子节点并且sum累加到了目标和，返回true，只要有一条路径是true最终就会返回true。