【牛客 - 剑指offer】JZ34 二叉树中和为某一值的路径(二) Java实现 两种方案

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 树 - JZ34 二叉树中和为某一值的路径(二)

题目

思路 & 代码

题目主要信息

• 给出一棵树的根节点指针，和一个期待值

• 要在这棵树中找出从根节点到叶子节点的路径上的节点值之和等于该期待值的路径，找出所有这样的路径并返回

方案一 深度优先搜索dfs

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始化点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路

从根节点开始向左右子树进行递归，递归函数中需要处理的是：

1. 当前路径path要更新

2. 当前的目标值expectNumber要迭代，减去当前节点的值

3. 若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中

注意

• 在提交的时候需要删掉@Test标识的方法，删除import org.junit.Test;这一行导包

• 擅用Debug功能

• 我认为需要注意的是ret.add(new ArrayList<>(path));必须创建一个新的arrayList来存放path，如果只是把path添加到ret中，在对path进行修改时，ret中存储的path也会相应更改，产生错误

import org.junit.Test;

import java.util.*;
import java.util.ArrayList;

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * 

 * public TreeNode(int val) {
 * this.val = val;
 * 

 * }
 * 

 * }
 */
public class Solution {

    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<>();

    void dfs(TreeNode node, int number) {
        if (node == null) {
            return;
        }
        //路径更新
        path.add(node.val);
        //number更新
        number -= node.val;
        //如果当前是叶子节点，且该条路的值达到了expectNumber
        if (node.right == null && node.left == null && number == 0) {
            ret.add(new ArrayList<>(path));
        }

        //遍历左子树
        dfs(node.left, number);
        //遍历右子树
        dfs(node.right, number);
        path.remove(path.size() - 1);

    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }

    @Test
    public void test() {
        TreeNode n1 = new TreeNode(10);
        TreeNode n2 = new TreeNode(5);
        TreeNode n3 = new TreeNode(12);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(7);

        n1.left = n2;
        n1.right = n3;

        n2.left = n4;
        n2.right=n5;

        ArrayList<ArrayList<Integer>> arrayLists = FindPath(n1, 22);
        System.out.println(arrayLists);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

方案二 广度优先搜索bfd

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名

• 元素入队，将新元素加在队列的队尾

• 元素出队，将队首元素取出，它的后一个为新的队首

思路

深度优先搜索是优先一条路走到底，而广度优先搜索是按照二叉树的层进行搜索，因此路径需要逐层进行记录，我们引入队列来维护这个逐层路径的信息

• pathQ存储了所有的路径

• 当遍历到叶子结点的时候，把当前的路径拿出来，检查所有节点的加和是不是和形参expectNumber

  • 满足条件的话，则把这个队列，加入ret

import org.junit.Test;

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {

        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        //存储路径和存储节点的是对应的
        //存储路径，所有情况的列表总和
        LinkedList<ArrayList<Integer>> pathQ = new LinkedList<>();
        //存储节点
        LinkedList<TreeNode> nodeQ = new LinkedList<>();

        pathQ.add(new ArrayList<Integer>(Arrays.asList(root.val)));
        nodeQ.add(root);

        while (!nodeQ.isEmpty()) {
            //poll 查询并移除第一个元素
            ArrayList<Integer> curPath = pathQ.poll();
            TreeNode curNode = nodeQ.poll();
            if (curNode.left == null && curNode.right == null) {
                ArrayList<Integer> l = curPath;
                int sum = 0;
                for (Integer integer : l) {
                    sum += integer;
                }
                if (sum == expectNumber) {
                    ret.add(l);
                }
            }
            if (curNode.left != null) {
                //创建一个arrayList
                ArrayList<Integer> left = new ArrayList<>(curPath);

                //向left中添加当前节点的值
                left.add(curNode.left.val);

                pathQ.add(left);

                //节点路径添加left节点
                nodeQ.add(curNode.left);
            }
            if (curNode.right != null) {
                ArrayList<Integer> right = new ArrayList<>(curPath);

                right.add(curNode.right.val);

                pathQ.add(right);

                nodeQ.add(curNode.right);
            }

        }
        return ret;
    }

    @Test
    public void test() {
        TreeNode n1 = new TreeNode(10);
        TreeNode n2 = new TreeNode(5);
        TreeNode n3 = new TreeNode(12);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(7);

        n1.left = n2;
        n1.right = n3;

        n2.left = n4;
        n2.right=n5;

        ArrayList<ArrayList<Integer>> arrayLists = FindPath(n1, 22);
        System.out.println(arrayLists);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79