LeetCode--路径总和（二叉树路径总和回溯法）

路径总和

路径总和1

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

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

示例:

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

/ \

4 8

/ / \

11 13 4

/ \ \

7 2 1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路1 双栈

/**
 * @Author liuhaidong
 * @Description 运用栈的方式
 * @param
 * @Date 12:08 2019/10/8 0008
 */
public static boolean hasPathSum1(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    Stack<TreeNode> path = new Stack<>();
    //存放节点
    Stack<Integer> sub = new Stack<>();
    //存放节点的值
    path.push(root);
    sub.push(root.val);
    while(!path.isEmpty()){
        TreeNode temp = path.pop();
        int tempVal = sub.pop();

        if(temp.left == null && temp.right == null) {
            if (tempVal == sum) {
                return true;
            }
        }else {
                if(temp.left != null){
                    path.push(temp.left);
                    sub.push(temp.left.val + tempVal);
                }
                if(temp.right != null){
                    path.push(temp.right);
                    sub.push(temp.right.val + tempVal);
                }
            }
        }

    return false;
}

递归

最直接的方法就是利用递归，遍历整棵树：如果当前节点不是叶子，对它的所有孩子节点，递归调用 hasPathSum 函数，其中 sum 值减去当前节点的权值；如果当前节点是叶子，检查 sum 值是否为 0，也就是是否找到了给定的目标和。

（从根节点开始，每当遇到一个节点的时候，从目标值里扣除节点值，一直到叶子节点判断目标值是不是被扣完）

class Solution {
  public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null){
     //这个地方是防止出现return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
      //里面root.left,root.right为空的情况
      return false;
    }

    sum -= root.val;
    if ((root.left == null) && (root.right == null))
      return (sum == 0);
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
  }
}

主函数

public static void main(String[] args) {
    TreeNode root = new TreeNode(5);
    TreeNode node1 = new TreeNode(4);
    TreeNode node2 = new TreeNode(8);
    TreeNode node3 = new TreeNode(11);
    TreeNode node4 = new TreeNode(7);
    TreeNode node5 = new TreeNode(2);
    TreeNode node6 = new TreeNode(13);
    TreeNode node7 = new TreeNode(4);
    TreeNode node8 = new TreeNode(1);
    root.left=node1;
    root.right=node2;
    node1.left=node3;
    node3.left=node4;
    node3.right=node5;
    node2.left=node6;
    node2.right=node7;
    node7.right=node8;
    System.out.println(hasPathSum1(root,22));
}

public class TreeNode {
          int val;
     TreeNode left;
     TreeNode right;
      TreeNode(int x) { val = x; }

}

路径总和2

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

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

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

5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

[
   [5,4,11,2],
   [5,8,4,5]
]

public static void main(String[] args) {
        TreeNode root1 = new TreeNode(10);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(12);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(7);
//        TreeNode node5 = new TreeNode(6);
//        TreeNode node6 = new TreeNode(7);
        root1.left=node1;
        root1.right=node2;
        node1.left =node3;
        node1.right = node4;
//        node2.left = node5;
//        node2.right = node6;
        System.out.println(pathSum(root1,22));
    }
    public static List<List<Integer>> paths = new ArrayList<>();
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        go(root,0,sum,new ArrayList<>());
        return paths;
    }
 
    public static void go(TreeNode node,int sum,int target,ArrayList<Integer> path){
        if(node==null){
            return;
        }
        sum+=node.val;
        path.add(node.val);
        //判断该路径和是否符合目标值
        if(sum==target&&node.left==null&&node.right==null){
            //因为要子节点，所以它的左子树和右子树必须为null
            paths.add(new ArrayList<>(path));
        }else{
            go(node.left,sum,target,path);
            go(node.right,sum,target,path);
        }
        //回溯
        path.remove(path.size()-1);
    }