2023年6月22日发(作者：)

【算法设计与分析（课后答案）】ListTree的递归1对于不带头结点的单链表L，设计⼀个递归算法正序输出所有结点值。public class Solution1 { public void printL(ListNode node) { if (node == null) { return; } n(); printL(); }}2对于不带头结点的单链表L，设计⼀个递归算法逆序输出所有结点值。public class Solution2 { public void printL(ListNode node) { if (node == null) { return; } printL(); n(); }}3对于不带头结点的⾮空单链表L，设计⼀个递归算法返回最⼤结点的地址（假设这样的结点唯⼀）。public class Solution3 { public ListNode findMax(ListNode node) { if ( == null) { return node; } return > findMax().val ? node : findMax(); }}4对于不带头结点的单链表L，设计⼀个递归算法返回第⼀个值为x的结点的地址，如果没有这样的结点就返回null。public class Solution4 { public ListNode findNode(ListNode node, int target) { if (node == null) { return null; } if ( == target) { return node; } return findNode(, target); }}5对于不带头结点的单链表L，设计⼀个递归算法删除第⼀个值为x的结点。public class Solution5 { /** *

虽说是递归，本质还是双/三指针的向右滑动 *

设置⼀个dummy头结点很有必要 */ public void deleteNode(ListNode head, int target) { ListNode dummy = new ListNode(-1); = head; delete(dummy, head, target); } private void delete(ListNode pre, ListNode node, int target) { if (node == null) { return; } if ( == target) { = ; return; } delete(node, , target); }}6假设⼆叉树采⽤⼆叉链存储结构存放，结点值为int类型，设计⼀个递归算法求⼆叉树bt中所有叶⼦结点之和。public class Solution6 { public int nodeSum(TreeNode node) { if (node == null) { return 0; } if ( == null && == null) { return ; } return nodeSum() + nodeSum(); }}7假设⼆叉树采⽤⼆叉链存储结构存放，结点值为int类型，设计⼀个递归算法求⼆叉树bt中所有结点值⼤于等于k的结点个数。public class Solution7 { public int countNode(TreeNode node, int k) { if (node == null) { return 0; } return ( >= k ? 1 : 0) + countNode(, k) + countNode(, k); }}8假设⼆叉树采⽤⼆叉链存储结构存放，所有结点值均不相同，设计⼀个递归算法值为x的结点的层次（跟节点层次为1），若没有找到这样的结点则返回0。public class Solution8 { public int findLayerOfK(TreeNode node, int k, int level) { if (node == null) { return 0; } if ( == k) { return level; } int t1 = findLayerOfK(, k, level + 1); int t2 = findLayerOfK(, k, level + 1); return t1 != 0 ? t1 : t2; }}