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

解题前困惑：

题目是要找出是否有某一路径和为sum，但是，很多情况都有可能返回false（比如遍历到叶子节点的空节点，遍历到叶子节点路径也不为目标sum等等），怎么就通过 判断(sum - root.val ==0), 的递归过程，返回true的？

阿哈时刻：

关键是前序遍历的过程中，解决了如下几个问题，扫除了我上面的困惑。

1、某一条路径的叶子节点，或者叶子节点的空节点，返回false都没有关系，应该return 的时候是 "||" 运算，只要左右子树有一边有就可以！

2、在visit T的时候，通过判断 root.left == null && root.right == null 来定位到子节点。

解题思路：

1、使用前序遍历的方法， if(visitT)返回值 / if(左节点) || if(右节点) 返回值。

2、visitT的时候，通过判断 root.left == null && root.right == null 来定位到子节点

3、 if(左节点) || if(右节点) 返回值，使用 || 或运算符，就可以把可能的路径找出来！

解题思路：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 这道题就是前序遍历的一种变种
     * 思路：遍历
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    //疑惑，递归该如何判断，前值遍历如何判断？
    // root == null 有可能传入就为空，还有就是到叶子节点的情况，如何区别？
    // 如何处理 左右自己节点的递归判断，sum - root.val 是怎么做到这样的判断的
    // 啊哈时刻：关键在于 || 运算符，只有一条分支有，就可以，其他都是false都没关系
    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);
    }

    /**
     * 使用记录路径来实现的功能
     */
    public boolean hasPathSum2 (TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        dfs(root, sum, res);
        return isFound;
    }

    boolean isFound = false;

    void dfs(TreeNode root, int sum, ArrayList<Integer> res) {
        // 到底了，判断res值是否为sum？
        if (root == null) {
            int path = 0;
            for (int i = 0; i < res.size(); i++) {
                path += res.get(i);
            }
            if (sum == path && res.size() > 1) {
                isFound = true;
            }
            return;
        }

        if (isFound) {
            return;
        }

        res.add(root.val);
        dfs(root.left, sum, res);
        dfs(root.right, sum, res);

        if (isFound) {
            return;
        }

        res.remove(res.size() - 1);
    }
}