递归 is all I hate

递归🐢

递归讲究的就是一个自信，相信自己的函数定义和它的return值，做下去，wow amazing，你就得到了结果

递归算法的时间复杂度 = 递归的次数 x 函数本身的时间复杂度

递归算法的空间复杂度 = 递归堆栈的深度 + 算法申请的存储空间

或者再说得直观一点：

递归算法的时间复杂度 = 递归树的节点个数 x 每个节点的时间复杂度

递归算法的空间复杂度 = 递归树的高度 + 算法申请的存储空间

例题

226. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode invertTree(TreeNode root) {
    TreeNode res = dfs(root);
    return res;
}

private TreeNode dfs(TreeNode cur) {
    if (cur == null) return null;
    TreeNode leftSwappedResult = dfs(cur.left);
    TreeNode rightSwappedResult = dfs(cur.right);
    cur.left = rightSwappedResult;
    cur.right = leftSwappedResult;
    return cur;
}