二叉树之路径

1. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

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

示例: 257.二叉树的所有路径1

1. 题解

本题本质是回溯算法

1. f(node)
2. 终止条件 --if(node==null) path加入– ,应该是到叶子节点加入
3. 剪枝 无
4. 单层递归
5. 注意点 先加入sb
   path(加入节点)
   f(left)
   f(right) //隐含回溯

2. 代码

 private ArrayList<String > res=new ArrayList<String >();
    //30. 二叉树的所有路径
    public List<String> binaryTreePaths(TreeNode root) {
        if (root==null){
            return res;
        }
        binaryTreePathsTB(root,new StringBuilder());
        return res;
    }

    public void binaryTreePathsTB(TreeNode node,StringBuilder sb) {
          sb.append(String.valueOf(node.val));
        sb.append('-');
        sb.append('>');
        if (node.left==null&&node.right==null){
            StringBuilder sb1 = new StringBuilder(sb);
            sb1.delete(sb1.length() - 2, sb.length());
             res.add(sb1.toString());
           // System.out.println(sb.toString());
             return;
        }

        if (node.left!=null){
            binaryTreePathsTB(node.left,sb);
            sb.delete(sb.length()-3,sb.length());
        }

        if (node.right!=null){
            binaryTreePathsTB(node.right,sb);
            sb.delete(sb.length()-3,sb.length());

        }

3. 正确代码

上一个代码使用sb删除时,如果是两位数,只能删除1个char

 public List<String> binaryTreePaths(TreeNode root) {
        if (root==null){
            return res;
        }
        ArrayList<String> path = new ArrayList<>();
        binaryTreePathsTB02(root,path);
        return res;
    }
    public void binaryTreePathsTB02(TreeNode node,ArrayList<String> path) {
        path.add(String.valueOf(node.val));
        path.add("->");
        if (node.left==null&&node.right==null){
            List<String> list = path.subList(0, path.size() - 1);
            StringBuilder sb = new StringBuilder();
            for (String s : list) {
                sb.append(s);
            }
            res.add(sb.toString());
            return;
        }

        if (node.left!=null){
            binaryTreePathsTB02(node.left,path);
            path.remove(path.size()-1);
            path.remove(path.size()-1);
        }

        if (node.right!=null){
            binaryTreePathsTB02(node.right,path);
            path.remove(path.size()-1);
            path.remove(path.size()-1);
        }
    }
			

2. 是否存在路径和=K的路径

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

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

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

1. 二叉树路径问题模板

1. 要先加入节点,为的是判断中止条件使,node.left!=null 时,保证node已经加入路径
2. 终止条件 (node.left!=null)&&node.right!=null
3. 单层递归
   if(左不空){
   剪枝
   f(左),
   path.remove(最后一个节点)
   }

if(右不空){
剪枝
f(右),
path.remove(最后一个节点)
}

4. 这种先加入,在子节点执行完后回溯,最后根节点一定保存在path中.因为回溯在if语句中,所以只能回溯子节点

2. 代码

 int sum=0;
      boolean isContinus=true;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        ArrayList<Integer> path = new ArrayList<>();
        if(root==null){
            return false;
        }

         hasPathSumTB02(root,targetSum,path);
          System.out.println(path);
         return !isContinus;
    }


  
    public void hasPathSumTB02(TreeNode node, int targetSum, ArrayList<Integer> path) {
        path.add(node.val);  //先加入
        sum+=node.val;
         // System.out.println(sum);
        if (node.left==null&&node.right==null){
          
            if (sum==targetSum){
               isContinus=false;
            }
            return;
        }
        if (isContinus&&node.left!=null){                                                                                       
            hasPathSumTB02(node.left, targetSum, path);
            sum-=node.left.val; // 这实际删除的是子节点,父节点是根本不会被删除
            path.remove(path.size()-1);
        }

        if (isContinus&&node.right!=null){
           hasPathSumTB02(node.right, targetSum, path);
            sum-=node.right.val;
            path.remove(path.size()-1);
        }
    }