要点

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

举例

  • 反转链表

    • 当前递归函数的作用：反转链表，并返回新的头结点。
    • 当前状态和下一递归状态的关系：递归调用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;
      }
  }