LeetCode热题100五138. 随机链表的复制题目详情https://leetcode.cn/problems/copy-list-with-random-pointer/给你一个长度为n的链表每个节点包含一个额外增加的随机指针random该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。 深拷贝应该正好由n个全新节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如如果原链表中有X和Y两个节点其中X.random -- Y。那么在复制链表中对应的两个节点x和y同样有x.random -- y。返回复制链表的头节点。用一个由n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示val一个表示Node.val的整数。random_index随机指针指向的节点索引范围从0到n-1如果不指向任何节点则为null。你的代码只接受原链表的头节点head作为传入参数。示例 1输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2输入head [[1,1],[2,1]] 输出[[1,1],[2,1]]示例 3输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]]解答过程想到的处理办法是遍历一遍后记录旧节点用于拼装新节点是查找旧节点的random值publicNodecopyRandomList(Nodehead){ArrayListNodeoldNodesnewArrayList();ArrayListNodenewNodesnewArrayList();NodennewNode(-1);Nodemn;while(head!null){oldNodes.add(head);newNodes.add(newNode(head.val));headhead.next;}for(inti0;ioldNodes.size();i){n.nextnewNodes.get(i);NoderandomoldNodes.get(i).random;if(random!null){newNodes.get(i).randomnewNodes.get(oldNodes.indexOf(random));}else{newNodes.get(i).randomnull;}nn.next;}returnm.next;}148. 排序链表题目详情https://leetcode.cn/problems/sort-list/给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3] 输出[1,2,3,4]示例 2输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]示例 3输入head [] 输出[]解答过程思路是遍历出节点随后排序重新组装链表publicListNodesortList(ListNodehead){ArrayListListNodenodesnewArrayList();while(head!null){nodes.add(head);headhead.next;}nodes.sort(newComparatorListNode(){Overridepublicintcompare(ListNodeo1,ListNodeo2){returno1.val-o2.val;}});ListNodelnnewListNode(-1);ListNodelln;for(ListNodenode:nodes){ln.nextnode;lnln.next;ln.nextnull;}returnl.next;}146. LRU 缓存题目详情https://leetcode.cn/problems/lru-cache/请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以O(1)的平均时间复杂度运行。示例输入 [LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4解答过程publicclassLRUCacheextendsLinkedHashMapInteger,Integer{intcapacity;publicLRUCache(intcapacity){// super(初始容量, 负载因子, 访问顺序)// 1. capacity初始容量设为缓存上限// 2. 0.75F负载因子HashMap 默认值当元素数达到 75% 时扩容// 3. true开启「访问顺序」模式核心super(capacity,0.75F,true);this.capacitycapacity;}publicintget(intkey){returnsuper.getOrDefault(key,-1);}publicvoidput(intkey,intvalue){super.put(key,value);}OverrideprotectedbooleanremoveEldestEntry(Map.EntryInteger,Integereldest){returnthis.size()capacity;}}102. 二叉树的层序遍历题目详情https://leetcode.cn/problems/binary-tree-level-order-traversal/给你二叉树的根节点root返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。示例 1输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]]示例 2输入root [1] 输出[[1]]示例 3输入root [] 输出[]解答过程看了官方解题思路才写出来本来想法是每次数组去存节点但是其实用队列更好点publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerlistsnewArrayList();if(rootnull){returnlists;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){ArrayListIntegerintegersnewArrayList();intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.poll();integers.add(node.val);if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}}lists.add(integers);}returnlists;}98. 验证二叉搜索树题目详情https://leetcode.cn/problems/validate-binary-search-tree/给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1输入root [2,1,3] 输出true示例 2输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是 5 但是右子节点的值是 4 。解答过程最初想法是每次递归判断左右节点的值但是始终有些case不通过看了官方解答确实应该在每次遍历的时候计算最大值、最小值验证publicbooleanisValidBST(TreeNoderoot){if(rootnull||(root.leftnullroot.rightnull)){returntrue;}returnvalidBST(root,Long.MAX_VALUE,Long.MIN_VALUE);}publicbooleanvalidBST(TreeNoderoot,longlargest,longsmallest){if(rootnull){returntrue;}System.out.println(largestroot.valsmallest);if(root.valsmallest||root.vallargest){returnfalse;}returnvalidBST(root.left,root.val,smallest)validBST(root.right,largest,root.val);}230. 二叉搜索树中第 K 小的元素题目详情https://leetcode.cn/problems/kth-smallest-element-in-a-bst/给定一个二叉搜索树的根节点root和一个整数k请你设计一个算法查找其中第k小的元素k从 1 开始计数。示例 1输入root [3,1,4,null,2], k 1 输出1示例 2输入root [5,3,6,2,4,null,null,1], k 3 输出3解答过程第一个想法是中序遍历排序取出值publicintkthSmallest(TreeNoderoot,intk){ArrayListIntegerarrayListnewArrayList();inorder(root,arrayList);arrayList.sort(newComparatorInteger(){Overridepublicintcompare(Integero1,Integero2){returno1-o2;}});returnarrayList.get(k-1);}publicvoidinorder(TreeNoderoot,ArrayListIntegerarrayList){if(rootnull){return;}inorder(root.left,arrayList);arrayList.add(root.val);inorder(root.right,arrayList);}199. 二叉树的右视图题目详情https://leetcode.cn/problems/binary-tree-right-side-view/给定一个二叉树的根节点root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例 1**输入**root [1,2,3,null,5,null,4]输出[1,3,4]解释示例 2**输入**root [1,2,3,4,null,null,null,5]输出[1,3,4,5]解释示例 3**输入**root [1,null,3]输出[1,3]示例 4**输入**root []输出[]解答过程利用层序遍历每次存储每行最后一个元素publicListIntegerrightSideView(TreeNoderoot){ArrayListIntegerarrayListnewArrayList();if(rootnull){returnarrayList;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.poll();if(isize-1){arrayList.add(node.val);}if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}}}returnarrayList;}114. 二叉树展开为链表题目详情https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/给你二叉树的根结点root请你将它展开为一个单链表展开后的单链表应该同样使用TreeNode其中right子指针指向链表中下一个结点而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。示例 1输入root [1,2,5,3,4,null,6] 输出[1,null,2,null,3,null,4,null,5,null,6]示例 2输入root [] 输出[]示例 3输入root [0] 输出[0]解答过程首先先序遍历然后重新重组节点publicvoidflatten(TreeNoderoot){ArrayListTreeNodenodesnewArrayList();if(rootnull){return;}preorder(root,nodes);for(inti0;inodes.size();i){nodes.get(i).leftnull;if(i0){nodes.get(i-1).rightnodes.get(i);}}}publicvoidpreorder(TreeNoderoot,ArrayListTreeNodenodes){if(rootnull){return;}nodes.add(root);preorder(root.left,nodes);preorder(root.right,nodes);}105. 从前序与中序遍历序列构造二叉树题目详情https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:输入: preorder [-1], inorder [-1] 输出: [-1]解题过程看了官方答案写出来的核心思路是确定根节点随后根据前序、中序不断构建树HashMapInteger,IntegerhashMapnewHashMap();publicTreeNodebuildTree(int[]preorder,int[]inorder){for(inti0;iinorder.length;i){hashMap.put(inorder[i],i);}returnbuildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);}publicTreeNodebuildTree(int[]preorder,int[]inorder,intpreStart,intpreEnd,intinStart,intinEnd){if(preStartpreEnd){returnnull;}// 根节点是前序数组的第一个元素寻找根节点在中序数组中的索引intindexhashMap.get(preorder[preStart]);// 构建节点TreeNodetreeNodenewTreeNode(inorder[index]);// 左子树范围intsizeindex-inStart;// 左右节点树treeNode.leftbuildTree(preorder,inorder,preStart1,preStartsize,inStart,index-1);treeNode.rightbuildTree(preorder,inorder,preStartsize1,preEnd,index1,inEnd);returntreeNode;}437. 路径总和 III题目详情https://leetcode.cn/problems/path-sum-iii/给定一个二叉树的根节点root和一个整数targetSum求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。示例 1输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8 输出3 解释和等于 8 的路径有 3 条如图所示。示例 2输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出3解答过程看了半天没看出来解法看了官方的解答才写出来外层递归pathSum 方法遍历二叉树的每个节点把每个节点当作 “路径起点”内层递归rootSum 方法以某个节点为起点向下遍历所有路径统计和为targetSum的路径数publicintpathSum(TreeNoderoot,inttargetSum){if(rootnull){return0;}// 统计以当前root为起点的符合条件的路径数intresultsum(root,targetSum);// 递归统计以左右子节点为起点的路径数resultpathSum(root.left,targetSum);resultpathSum(root.right,targetSum);returnresult;}publicintsum(TreeNoderoot,longtargetSum){intresult0;if(rootnull){return0;}intvalroot.val;// 如果当前节点值等于剩余目标和说明找到1条有效路径if(valtargetSum){result;}// 递归左右子节点剩余目标和 原目标和 - 当前节点值resultsum(root.left,targetSum-val);resultsum(root.right,targetSum-val);returnresult;}
LeetCode热题100（五）
LeetCode热题100五138. 随机链表的复制题目详情https://leetcode.cn/problems/copy-list-with-random-pointer/给你一个长度为n的链表每个节点包含一个额外增加的随机指针random该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。 深拷贝应该正好由n个全新节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如如果原链表中有X和Y两个节点其中X.random -- Y。那么在复制链表中对应的两个节点x和y同样有x.random -- y。返回复制链表的头节点。用一个由n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示val一个表示Node.val的整数。random_index随机指针指向的节点索引范围从0到n-1如果不指向任何节点则为null。你的代码只接受原链表的头节点head作为传入参数。示例 1输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2输入head [[1,1],[2,1]] 输出[[1,1],[2,1]]示例 3输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]]解答过程想到的处理办法是遍历一遍后记录旧节点用于拼装新节点是查找旧节点的random值publicNodecopyRandomList(Nodehead){ArrayListNodeoldNodesnewArrayList();ArrayListNodenewNodesnewArrayList();NodennewNode(-1);Nodemn;while(head!null){oldNodes.add(head);newNodes.add(newNode(head.val));headhead.next;}for(inti0;ioldNodes.size();i){n.nextnewNodes.get(i);NoderandomoldNodes.get(i).random;if(random!null){newNodes.get(i).randomnewNodes.get(oldNodes.indexOf(random));}else{newNodes.get(i).randomnull;}nn.next;}returnm.next;}148. 排序链表题目详情https://leetcode.cn/problems/sort-list/给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3] 输出[1,2,3,4]示例 2输入head [-1,5,3,4,0] 输出[-1,0,3,4,5]示例 3输入head [] 输出[]解答过程思路是遍历出节点随后排序重新组装链表publicListNodesortList(ListNodehead){ArrayListListNodenodesnewArrayList();while(head!null){nodes.add(head);headhead.next;}nodes.sort(newComparatorListNode(){Overridepublicintcompare(ListNodeo1,ListNodeo2){returno1.val-o2.val;}});ListNodelnnewListNode(-1);ListNodelln;for(ListNodenode:nodes){ln.nextnode;lnln.next;ln.nextnull;}returnl.next;}146. LRU 缓存题目详情https://leetcode.cn/problems/lru-cache/请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以O(1)的平均时间复杂度运行。示例输入 [LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4解答过程publicclassLRUCacheextendsLinkedHashMapInteger,Integer{intcapacity;publicLRUCache(intcapacity){// super(初始容量, 负载因子, 访问顺序)// 1. capacity初始容量设为缓存上限// 2. 0.75F负载因子HashMap 默认值当元素数达到 75% 时扩容// 3. true开启「访问顺序」模式核心super(capacity,0.75F,true);this.capacitycapacity;}publicintget(intkey){returnsuper.getOrDefault(key,-1);}publicvoidput(intkey,intvalue){super.put(key,value);}OverrideprotectedbooleanremoveEldestEntry(Map.EntryInteger,Integereldest){returnthis.size()capacity;}}102. 二叉树的层序遍历题目详情https://leetcode.cn/problems/binary-tree-level-order-traversal/给你二叉树的根节点root返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。示例 1输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]]示例 2输入root [1] 输出[[1]]示例 3输入root [] 输出[]解答过程看了官方解题思路才写出来本来想法是每次数组去存节点但是其实用队列更好点publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerlistsnewArrayList();if(rootnull){returnlists;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){ArrayListIntegerintegersnewArrayList();intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.poll();integers.add(node.val);if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}}lists.add(integers);}returnlists;}98. 验证二叉搜索树题目详情https://leetcode.cn/problems/validate-binary-search-tree/给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1输入root [2,1,3] 输出true示例 2输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是 5 但是右子节点的值是 4 。解答过程最初想法是每次递归判断左右节点的值但是始终有些case不通过看了官方解答确实应该在每次遍历的时候计算最大值、最小值验证publicbooleanisValidBST(TreeNoderoot){if(rootnull||(root.leftnullroot.rightnull)){returntrue;}returnvalidBST(root,Long.MAX_VALUE,Long.MIN_VALUE);}publicbooleanvalidBST(TreeNoderoot,longlargest,longsmallest){if(rootnull){returntrue;}System.out.println(largestroot.valsmallest);if(root.valsmallest||root.vallargest){returnfalse;}returnvalidBST(root.left,root.val,smallest)validBST(root.right,largest,root.val);}230. 二叉搜索树中第 K 小的元素题目详情https://leetcode.cn/problems/kth-smallest-element-in-a-bst/给定一个二叉搜索树的根节点root和一个整数k请你设计一个算法查找其中第k小的元素k从 1 开始计数。示例 1输入root [3,1,4,null,2], k 1 输出1示例 2输入root [5,3,6,2,4,null,null,1], k 3 输出3解答过程第一个想法是中序遍历排序取出值publicintkthSmallest(TreeNoderoot,intk){ArrayListIntegerarrayListnewArrayList();inorder(root,arrayList);arrayList.sort(newComparatorInteger(){Overridepublicintcompare(Integero1,Integero2){returno1-o2;}});returnarrayList.get(k-1);}publicvoidinorder(TreeNoderoot,ArrayListIntegerarrayList){if(rootnull){return;}inorder(root.left,arrayList);arrayList.add(root.val);inorder(root.right,arrayList);}199. 二叉树的右视图题目详情https://leetcode.cn/problems/binary-tree-right-side-view/给定一个二叉树的根节点root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例 1**输入**root [1,2,3,null,5,null,4]输出[1,3,4]解释示例 2**输入**root [1,2,3,4,null,null,null,5]输出[1,3,4,5]解释示例 3**输入**root [1,null,3]输出[1,3]示例 4**输入**root []输出[]解答过程利用层序遍历每次存储每行最后一个元素publicListIntegerrightSideView(TreeNoderoot){ArrayListIntegerarrayListnewArrayList();if(rootnull){returnarrayList;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){TreeNodenodequeue.poll();if(isize-1){arrayList.add(node.val);}if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}}}returnarrayList;}114. 二叉树展开为链表题目详情https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/给你二叉树的根结点root请你将它展开为一个单链表展开后的单链表应该同样使用TreeNode其中right子指针指向链表中下一个结点而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。示例 1输入root [1,2,5,3,4,null,6] 输出[1,null,2,null,3,null,4,null,5,null,6]示例 2输入root [] 输出[]示例 3输入root [0] 输出[0]解答过程首先先序遍历然后重新重组节点publicvoidflatten(TreeNoderoot){ArrayListTreeNodenodesnewArrayList();if(rootnull){return;}preorder(root,nodes);for(inti0;inodes.size();i){nodes.get(i).leftnull;if(i0){nodes.get(i-1).rightnodes.get(i);}}}publicvoidpreorder(TreeNoderoot,ArrayListTreeNodenodes){if(rootnull){return;}nodes.add(root);preorder(root.left,nodes);preorder(root.right,nodes);}105. 从前序与中序遍历序列构造二叉树题目详情https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:输入: preorder [-1], inorder [-1] 输出: [-1]解题过程看了官方答案写出来的核心思路是确定根节点随后根据前序、中序不断构建树HashMapInteger,IntegerhashMapnewHashMap();publicTreeNodebuildTree(int[]preorder,int[]inorder){for(inti0;iinorder.length;i){hashMap.put(inorder[i],i);}returnbuildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);}publicTreeNodebuildTree(int[]preorder,int[]inorder,intpreStart,intpreEnd,intinStart,intinEnd){if(preStartpreEnd){returnnull;}// 根节点是前序数组的第一个元素寻找根节点在中序数组中的索引intindexhashMap.get(preorder[preStart]);// 构建节点TreeNodetreeNodenewTreeNode(inorder[index]);// 左子树范围intsizeindex-inStart;// 左右节点树treeNode.leftbuildTree(preorder,inorder,preStart1,preStartsize,inStart,index-1);treeNode.rightbuildTree(preorder,inorder,preStartsize1,preEnd,index1,inEnd);returntreeNode;}437. 路径总和 III题目详情https://leetcode.cn/problems/path-sum-iii/给定一个二叉树的根节点root和一个整数targetSum求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。示例 1输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8 输出3 解释和等于 8 的路径有 3 条如图所示。示例 2输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出3解答过程看了半天没看出来解法看了官方的解答才写出来外层递归pathSum 方法遍历二叉树的每个节点把每个节点当作 “路径起点”内层递归rootSum 方法以某个节点为起点向下遍历所有路径统计和为targetSum的路径数publicintpathSum(TreeNoderoot,inttargetSum){if(rootnull){return0;}// 统计以当前root为起点的符合条件的路径数intresultsum(root,targetSum);// 递归统计以左右子节点为起点的路径数resultpathSum(root.left,targetSum);resultpathSum(root.right,targetSum);returnresult;}publicintsum(TreeNoderoot,longtargetSum){intresult0;if(rootnull){return0;}intvalroot.val;// 如果当前节点值等于剩余目标和说明找到1条有效路径if(valtargetSum){result;}// 递归左右子节点剩余目标和 原目标和 - 当前节点值resultsum(root.left,targetSum-val);resultsum(root.right,targetSum-val);returnresult;}
