阿飞算法|剑指offer-二叉树中和为某一值的路径(一)（多解法）

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

方法1:DFS

        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) return false;
            return dfs(root, sum);
        }

        private boolean dfs(TreeNode root, int sum) {
            //当前节点是叶子节点，开始比较val是否相等
            if (root.left == null && root.right == null && root.val == sum) return true;
            boolean res = false;
            //只要左右子树有一个是true即可
            if (root.left != null) res = res || dfs(root.left, sum - root.val);
            if (root.right != null) res = res || dfs(root.right, sum - root.val);
            return res;
        }

方法2:递归

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    //当前的节点是叶子节点，比较剩下的sum值是否相等
    if (root.left == null && root.right == null) return root.val == sum;
    //左右两棵子树只要一个符合即可
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

方法3:BFS

 public boolean hasPathSum4th(TreeNode root, int sum) {
        if (root == null) return false;
        LinkedList<TreeNode> nodeQueue = new LinkedList<>();
        LinkedList<Integer> numQueue = new LinkedList<>();
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        while (!nodeQueue.isEmpty()) {
            TreeNode curNode = nodeQueue.pop();
            Integer curNum = numQueue.pop();
            if (curNode.left == null && curNode.right == null && curNum == sum) return true;
            if (curNode.left != null) {
                nodeQueue.offer(curNode.left);
                numQueue.offer(curNum + curNode.left.val);
            }
            if (curNode.right != null) {
                nodeQueue.offer(curNode.right);
                numQueue.offer(curNum + curNode.right.val);
            }
        }
        return false;
    }