Algorithm-Recursive

引言：

递归解释

引例——数组求和问题

代码示例：

public class SumRecusion {

    // 暴露给用户调用的和函数
    public static int sum(int[] arr) {
        return sum(arr, 0);
    }

    // 真正调用的递归求和的和函数
    // 功能为计算arr[l ... n)范围内的数字和
    private static int sum(int[] arr, int l) {
        // 求解最基本的问题
        // 递归结束条件
        if (l == arr.length)
            return 0;
        // 把原问题转化为更小的问题（将从l开始计算的问题变成从l+1开始计算的问题）
        // 调用sum函数理解为一个和完成指定功能的子函数的调用
        return arr[l] + sum(arr, l + 1);
    }
}

总结（两步）：

• 递归结束条件

• 把原问题转换为更小的问题

链表与递归

问题示例：递归删除链表中某个元素值

代码示例：

public class RecursionRemoveElement {
    // 给定链表头节点head，递归删除其中的节点val，返回新的链表头节点
    public ListNode removeElements(ListNode head, int val){
        // 递归出口
        if(head == null)
            return null;

        /* 基本版
        ListNode res = removeElements(head.next, val);
        if(head.val == val)
            return res;
        else{
            head.next = res;
            return head;
        }
        */

        // 精简版
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

微观分析

小结

int func(传入数值) {
  if (终止条件) 
      return 最小子问题解;
  return func(缩小规模);
}

二叉树与递归

// N叉树
void traverse(TreeNode root){
    if(root == null)
        return;
    for(TreeNode child : root.children)
        traverse(child);
}
// 二叉树
void traverse(TreeNode root){
    if(root == null)
        return;
    traverse(root.leftNode);
    traverse(root.rightNode);
}

Leetcode437 PathSum III

给一棵二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的路径条数

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

这里涉及两层递归函数，一个是count函数，作用是该节点下有多少条路线，本质是二叉树遍历，递归该节点下存在的路径，pathSum函数也是二叉树遍历，是在遍历那个节点。

public class LeetCode437 {
    public int pathSum(TreeNode root, int sum){
        if(root == null)
            return 0;
        int rootPathSum = count(root,sum);
        int leftPathSum = pathSum(root.left,sum);
        int rightPathSum = pathSum(root.right,sum-root.val);
        return rootPathSum + leftPathSum + rightPathSum;
    }

    private int count(TreeNode root, int sum){
        if(root == null)
            return 0;
        int target = 0;
        if(root.val == sum)
            target = 1;
        int leftPath = count(root.left,sum-root.val);
        int rightPath = count(root.right,sum-root.val);
        return target + leftPath + rightPath;
    }
}

Leetcode226