二叉树的路径之和

问题1

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

原理

• 判断左子树或者右子树是否有符合条件的节点
• 递归的终止条件，当前节点为空返回false，当前节点的左右子节点为空并且sum==0

代码

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

注意事项

• 当前节点的左右子节点为空并且sum为0返回结果为true

问题2

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

原理

• 需要找到所有的路径，可以联想到回溯算法
• 结束条件是root==null 或者root.left==null&&root.right==null&&sum==0则是满足条件的路径

代码

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        backTrace(list,new ArrayList<>(),root,sum);
        return list;
    }

    private void backTrace( List<List<Integer>> list,List<Integer> clist,TreeNode root, int sum){
        if(root==null){
            return ;
        }

        clist.add(root.val);
        sum = sum - root.val;

        if(root.left==null&&root.right==null&&sum==0){
            list.add(new ArrayList<>(clist));
            return ;
        }
       if(root.left!=null){
           backTrace(list,clist,root.left,sum);
            clist.remove(clist.size()-1);
       }
       if(root.right!=null){
            backTrace(list,clist,root.right,sum);
            clist.remove(clist.size()-1);
       }
        
    }
}

注意事项

• 回溯算法需要考虑回退
• 其他的暂时未想到，后序会整理回溯算法

问题3

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

原理

• 不要求根节点，也不要求叶子节点，说明任意组合都可以
• 因此需要考虑两层递归，第一次递归处理当前节点往下找的情况，第二层递归处理当前节点的左子树和右子树
• 采用一个全局变量count记录最终的结果

代码

class Solution {
    int count = 0;
    public int pathSum(TreeNode root, int sum) {
        if(root==null){
            return 0;
        }
        findSum(root,sum);
        pathSum(root.left,sum);
        pathSum(root.right,sum);
        return count;
    }

    private void findSum(TreeNode root, int sum){
        if(root==null){
            return ;
        }
        sum = sum -root.val;
        if(sum==0){
            count++;
        }
        findSum(root.left,sum);
        findSum(root.right,sum);
    }
}

注意事项

• 需要考虑两层递归的设计与理解
• 全局变量count记录最终结果