失眠网 > [剑指offer][JAVA]面试题第[34]题[二叉树中和为某一值的路径][回溯]

[剑指offer][JAVA]面试题第[34]题[二叉树中和为某一值的路径][回溯]

时间：2022-11-12 03:18:29

【问题描述】[中等]

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。示例:给定如下二叉树，以及目标和 sum = 22，5/ \4 8/ / \11 13 4/ \ / \7 2 5 1返回:[[5,4,11,2],[5,8,4,5]]提示：节点总数 <= 10000

【解答思路】

1. 回溯

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {LinkedList<List<Integer>> res = new LinkedList<>();LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) {recur(root, sum);return res;}void recur(TreeNode root, int tar) {if(root == null) return;path.add(root.val);tar -= root.val;if(tar == 0 && root.left == null && root.right == null)res.add(new LinkedList(path));recur(root.left, tar);recur(root.right, tar);path.removeLast();}}

sum==target 作为出口

LinkedList<List<Integer>> res = new LinkedList<>();LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) {recur(root, sum, 0);return res;}void recur(TreeNode root, int sum,int tar) {if(root == null) return;path.add(root.val);tar += root.val;if(tar == sum && root.left == null && root.right == null)res.add(new LinkedList(path));recur(root.left,sum, tar);recur(root.right,sum, tar);path.removeLast();//回溯}

详细注释

/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode(int x) { val = x; }* }*/class Solution {public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> lists = new ArrayList<>();if(root == null) return lists;findPath(new ArrayList<Integer>(),root,sum,0,lists);return lists;}/** path:用于存放当前节点所在的路径（随着遍历一直在变动）*/private static void findPath(List<Integer> path, TreeNode node, int sum, int tempSum,List<List<Integer>> lists) {//到当前节点位置的路径的节点值的和tempSum += node.val;//path.add(node.val);if(tempSum == sum && node.left == null &&node.right == null) {//得到一个符合要求的路径时，创建一个新的ArrayList，拷贝当前路径到其中，并添加到lists中lists.add(new ArrayList(path));}if(node.left != null) {findPath(path,node.left,sum,tempSum,lists);//递归结束时，该留的路径已经记录了，不符合的路径也都不用理，删掉当前路径节点的值path.remove(path.size()-1);}if(node.right != null) {findPath(path,node.right,sum,tempSum,lists);//递归结束时，该留的路径已经记录了，不符合的路径也都不用理，删掉当前路径节点的值path.remove(path.size()-1);}}}

【总结】

1.浅拷贝深拷贝

2. res.add(new LinkedList(path))对比res.add(path)

res.add(path) 浅拷贝

res.add(new LinkedList(path)) 深拷贝

记录路径时若直接执行 res.append(path) ，则是将 path 列表对象加入了 res ；后续 path 对象改变时， res 中的 path 对象也会随之改变（因此肯定是不对的，本来存的是正确的路径 path ，后面又 append 又 pop 的，就破坏了这个正确路径）。list(path) 相当于新建并复制了一个 path 列表，因此不会受到 path 变化的影响。