剑指Offer(34) 二叉树中和为某一值的路径

发表于 | 分类于 | 阅读次数:
字数统计: 1.1k | 阅读时长 ≈ 4

二叉树中和为某一值的路径

题目

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始一直到也借点所经过的节点形成一条路径。

思路

  1. 假设找到了其中一条路径，达到叶结点后，由于没有指向父节点的指针，所以必须 提前创建一个链表 存储前面经过的节点。

  2. 由于从根节点出发，所以要想用到使用前序遍历。

  3. 利用链表存储节点，在该节点完成左右子树的路径搜索后（即递归函数结束，返回到其父节点后），要删除 该节点，从而记录别的路径。

具体实现：
通过前序遍历，从根节点出发，每次在链表中存储便利到的节点，若到达叶子节点，则根据所有节点的和是否等于输入的整数，判断是否打印输出。在当前节点访问结束后，递归函数将会返回到它的父节点，所以在函数退出之前，要删除链表中的当前节点，以确保返回父节点是，储存的路径刚好是从根节点到父节点。

改进：书中的代码是根据所有结点的和是否等于输入的整数，判断是否打印输出。其实没有这个必要，只需要在每次遍历到一个结点时，令目标整数等于自己减去当前结点的值，若到达根结点时，最终的目标整数等于0就可以打印输出。（描述得不是很清楚，就是相当于每个结点的目标整数不同，详见代码）

测试用例

  1. 功能测试（一条或者多条对应的路径，无对应路径，节点值为正负零）
  2. 特殊测试（根节点为null）

java代码

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

/**
 * @description:题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * @author: rhsphere
 * @since: 2019-07-11 16:58 by jdk 1.8
 */
public class PathInTree {
    public class TreeNode {
        int val = 0;
        TreeNode left, right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public void findPath(TreeNode root, int target) {
    	if (root == null)
    		return;
    	ArrayList<TreeNode> list = new ArrayList<>();
    	printPath(root, target, list);

    }

    private void printPath(TreeNode node, int target, ArrayList<Integer> list) {
    	if (node == null)
    		return;
    	list.add(node.val);
    	target -= node.val;
    	if (target == 0 && node.left == null && node.right == null) {
    		for (Integer integer : list) {
    			System.out.print(integer + " ");
    		}
    		System.out.println();
    	} else {
    		printPath(node.left, target, list);
    		printPath(node.right, target, list);
    	}
    	list.remove(list.size() - 1);
    }
}

牛客网代码

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
/*
 * 几个要点：
 * 1. 将nodeList和pathList定义成全局变量，避免在方法中的多次传递
 * 2. 在pathList中添加nodeList时，因为nodeList会不断变化，所以必须新建一个list存入
 *    复制ArrayList的方法：newList=new ArrayList<Integer>(oldList)(复制内容，而不是复制地址，
 *    注意与newList=oldList的区分）
 * 3. 在当前结点完成左右子树的路径搜索后，记得删除nodeList中的当前结点
 * 4. target是基本数据类型int，不会受到方法的影响而改变
 */
public class PathInTree2 {
    public static class TreeNode {
        int val = 0;
        TreeNode left, right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    private ArrayList<Integer> nodeList = new ArrayList<>();
    private ArrayList<ArrayList<Integer>> pathList = new ArrayList<>();

    pubilc ArrayList<ArrayList<Integer>> findPath(TreeNode node, int target) {
    	if (node == null)
    		return pathList;
    	nodelist.add(node.val);
    	target -= node.val;
    	if (target == 0 && node.left == null && node.right == null) {
    		int i = 0;
    		while (i < pathList.size() && nodeList.size() < pathList.get(i).size())
    			i++;
    		pathList.add(i, new ArrayList<Integer>(nodeList));
    	} else {
    		pathList = findPath(node.left, target);
    		pathList = findPath(node.right, target);
    	}
    	nodeList.remove(nodeList.size() - 1);
    	return pathList;
    }
}

总结

  1. 二叉树的许多题目都与遍历（包括层次遍历）有关，要深刻理解；根据节点的位置判断使用哪一种遍历。
  2. 而二叉树遍历过程没有父节点指针，要保存路径的话，需要创建容器存储之前的节点。
  3. 熟悉这道题中在每次递归函数结束前删除当前节点的操作，这可以确保返回到父节点时路径刚好是从根节点到父节点。
0%