二叉树中某值的路径

Leetcode：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof"GitHub:https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_27_pathSum/Solution.java路径求和到某个值在thebinarytree》问题描述：给定你的二叉树的根节点和一个整数target和targetSum，找到从根节点到叶子节点的所有路径，其总和等于给定的目标总和。难度：中叶节点是没有子节点的节点。示例1：输入：root=[5,4,8,11,null,13,4,7,2,null,null,5,1],targetSum=22输出：[[5,4,11,2],[5,8,4,5]]例2：输入：root=[1,2,3],targetSum=5输出：[]例3：输入：root=[1,2],targetSum=0输出:[]解题思路：》本题是典型的二叉树解法搜索题，采用回溯法求解，包括前序遍历+路径记录两部分。前序遍历：按照“根，左”的顺序,right",遍历树的所有节点。路径记录：在前序遍历中，记录从根节点到当前节点的路径。当路径为①根节点到叶子节点形成的路径和②每个节点的值之和等于目标值sum，则将这条路径添加到结果列表中。算法流程：pathSum(root,sum)功能：初始化：结果列表res，路径列表path。返回值：只返回res.recur(root,tar)函数：递归参数：当前节点root，currenttargetvaluetar终止条件：如果节点根为空，则直接返回。递归工作：路径更新：将当前节点值root.val添加到路径path中；目标值更新：tar=tar-root.val（即目标值tar从sum减为0）；路径记录：当①root为叶节点且②路径和等于目标值时，将这条路径加入res。先序遍历：递归左1右子节点。路径恢复：在向上回溯之前，需要将当前节点从路径中删除，即执行path.pop()。复杂度分析：时间复杂度O(N)：N为二叉树的节点数，前序遍历需要遍历所有节点。空间复杂度O(N)：在最坏情况下，当树退化为链表时，path存储所有树节点，使用O(N)额外空间。packagecom.nateshao.sword_offer.topic_27_pathSum;importjava.util.ArrayList;导入java.util.LinkedList；导入java.util.List；@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：二叉树中的和为一个A值路径*/publicclassSolution{publicstaticvoidmain(String[]args){TreeNodenode1=newTreeNode(10);TreeNodenode2=newTreeNode(5);TreeNodenode3=newTreeNode(12);TreeNodenode4=newTreeNode(4);TreeNodenode5=newTreeNode(7);node1.left=node2;node1.right=node3;node2.left=node4;node2.right=node5;Solutionp=newSolution();System.out.println(p.listAll);p.pathSum(node1,22);for(Listlist:p.listAll){for(inti:list){System.out.print(i+"");}System.out.println();}/***[]*1057*1012*//***************************************************************************************/privatestaticList>listAll=newArrayList<>();privatestaticList<;Integer>list=newArrayList<>();/***思路：先保存根节点，然后分别在左右子树中递归查找目标值，找到则到达叶节点，并打印路径中的值**@paramroot*@paramtarget*@return*/publicstaticList>pathSum(TreeNoderoot,inttarget){if(root==null)returnlistAll;list.add(root.val);target-=root.val;if(target==0&&root.left==null&&root.right==null){listAll.add(newArrayList<>(list));}pathSum(root.left,target);pathSum(root.right,target);list.remove(list.size()-1);returnlistAll;}/***************************特色答案***************************/LinkedList>res=newLinkedList<>();LinkedListpath=newLinkedList<>();publicList>pathSum2(TreeNoderoot,intsum){recur(root,sum);returnres;}voidrecur(TreeNoderoot,inttar){if(root==null)return;path.add(root.val);tar-=root.val;if(tar==0&&root.left==null&&root.right==null)res.add(newLinkedList(path));recur(root.left,tar);recur(root.right,tar);path.removeLast();}publicstaticclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}}