递归

要点

• 搞清楚递归函数的作用
• 处理当前状态和下一递归状态的关系
• 处理好递归的出口

举例

• 反转链表

  • 当前递归函数的作用：反转链表，并返回新的头结点。
  • 当前状态和下一递归状态的关系：递归调用ReverseList(head.next)，函数会返回新的头结点，我们需要处理好当前状态和下一状态的关系。
  • 递归的出口：如果head或者head.next为null，直接返回head；
  • 代码

      public class Solution {
          public ListNode ReverseList(ListNode head) {
              if (head == null || head.next == null) {
                  return head;
              }
              ListNode newHead = ReverseList(head.next);
              // 处理状态
              head.next.next = head;
              head.next = null;
              return newHead;
          }
      }

• 最近公共节点

  • 当前递归函数的作用：返回最近公共节点
  • 当前状态和下一递归状态的关系：判断lowestCommonAncestor(root.left)和lowestCommonAncestor(root.right)是否为null。如果两个都不为null，则返回当前节点；如果某一个为null，返回另一个节点；
  • 递归的出口：root为null或者root等于left或者root等于right；
  • 代码

      class Solution {
          public TreeNode lowestCommonAncestor(TreeNode root, TreeNode o1, TreeNode o2) {
              if (root == null || root == o1 || root == o2) {
                  return root;
              }
              TreeNode left = lowestCommonAncestor(root.left, o1, o2);
              TreeNode right = lowestCommonAncestor(root.right, o1, o2);
              if (left != null && right != null) {
                  return root;
              }
              if (left != null) {
                  return left;
              }
              if (right != null) {
                  return right;
              }
              return null;
          }
      }

• 最小的K个数

  • 当前递归函数的作用：排序前k个数，即在(left, right)范围，将key = arr[left]放置到合适的位置，使得左边的值都小于key，右边的值都大于key；

  • 当前状态和下一状态的关系：(left, i - 1)都是小于等于key，(i + 1, right)都是大于等于key。如果当前下标i等于k - 1，则可以直接return；如果当前下标i大于k - 1，则需要调用helper(arr, left, i - 1);如果当前下标小于k - 1，则递归调用helper(arr, i + 1, right)。

  • 递归的出口：left < right；

  • 代码

      public class Solution {
          private void quickSortImporvment(int[] nums, int left, int right, int k) {
              if (left < right) {
                  int randomIndex = new Random().nextInt(right - left + 1) + left;
                  swap(nums, left, randomIndex);
                  int i = left, j = right, key = nums[i];
                  while (i < j) {
                      while (i < j && nums[j] >= key) {
                          j--;
                      }
                      if (i < j) {
                          nums[i] = nums[j];
                      }
                      while (i < j && nums[i] <= key) {
                          i++;
                      }
                      if (i < j) {
                          nums[j] = nums[i];
                      }
                  }
                  nums[i] = key;
                  if (i == k - 1) {
                      return ;
                  } else if (i > k - 1) {
                      quickSortImporvment(nums, left, i - 1, k);
                  } else {
                      quickSortImporvment(nums, i + 1, right, k);
                  }
              }
          }
    
          private void swap(int[] arr, int index1, int index2) {
              int temp = arr[index1];
              arr[index1] = arr[index2];
              arr[index2] = temp;
          }
      }