By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、路径总和1

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

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

示例:

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

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

1.1、解题思路

类似于全排列，组合总和，

1.2、算法


public boolean hasPathSum(TreeNode root, int sum) {
    //因为后面是或者关系，所以只要有一个为true就可以了
    if (root == null) {
        return false;
    }
    if (root.val == sum && root.left ==null && root.right == null) {
        return true;
    }
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}


public TreeNode initTreeNode(){
    TreeNode treeNode1 = new TreeNode(7, null ,null);
    TreeNode treeNode2 = new TreeNode(2, null , null);
    TreeNode treeNode3 = new TreeNode(11, treeNode1, treeNode2);
    TreeNode treeNode4 = new TreeNode(1, null, null);
    TreeNode treeNode5 = new TreeNode(4, null, treeNode4);
    TreeNode treeNode6 = new TreeNode(13, null, null);
    TreeNode treeNode7 = new TreeNode(8, treeNode6, treeNode5);
    TreeNode treeNode8 = new TreeNode(4, treeNode3, null);
    TreeNode root = new TreeNode(5, treeNode8, treeNode7);
    return root ;
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;

    }
}

1.3、测试

@Test
public void test(){
    TreeNode treeNode = initTreeNode();
    System.out.println(hasPathSum(treeNode, 22));
}

2、路径总和1

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

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

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

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1 
    
返回:
[
   [5,4,11,2],
   [5,8,4,5]
]

1.1、解题思路

1.2、算法

public List<List<Integer>> pathSum(TreeNode root, int target) {

    List<List<Integer>> list = new ArrayList<>();
    hasPathSum(list, new LinkedList<>(), root, target);
    return list;
}

private void hasPathSum(List<List<Integer>> list, LinkedList linkedList, TreeNode root,  int target) {
    if (root == null){
        return;
    }
    linkedList.add(root.val);
    //后面加上判断节点的结束，防止提前结束
    if (target ==  root.val && root.left == null && root.right == null){
        list.add(new ArrayList<>(linkedList));
        return;
    }

    if (root.left != null) {
        hasPathSum(list, linkedList, root.left, target-root.val);
        linkedList.removeLast();
    }

    if (root.right != null) {
        hasPathSum(list, linkedList, root.right, target-root.val);
        linkedList.removeLast();
    }
}


public TreeNode initTreeNode(){
    TreeNode treeNode0 = new TreeNode(5, null , null);
    TreeNode treeNode1 = new TreeNode(7, null ,null);
    TreeNode treeNode2 = new TreeNode(2, null , null);
    TreeNode treeNode3 = new TreeNode(11, treeNode1, treeNode2);
    TreeNode treeNode4 = new TreeNode(1, null, null);
    TreeNode treeNode5 = new TreeNode(4, treeNode0, treeNode4);
    TreeNode treeNode6 = new TreeNode(13, null, null);
    TreeNode treeNode7 = new TreeNode(8, treeNode6, treeNode5);
    TreeNode treeNode8 = new TreeNode(4, treeNode3, null);
    TreeNode root = new TreeNode(5, treeNode8, treeNode7);
    return root ;
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;

    }
}

1.3、测试


    @Test
    public void test(){
        TreeNode treeNode = initTreeNode();
        System.out.println(pathSum(treeNode, 22));
    }

​

ContactAuthor