常用算法 — 递归

建立思维 #

理解递归的关键首先还是弄清楚二叉树的先序遍历、中序遍历和后序遍历的递归实现。任何递归可以说都处在这个模型中。

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

如果面试官明确要求不使用递归，那一般就是使用后进先出的栈来代替递归实现，可以参考二叉树专题中遍历二叉树的非递归实现。

如何画递归流程？ #

时间复杂度怎么计算？ #

用子问题个数乘以解决一个子问题需要的时间。

递归的缺点 #

递归可能会有重复计算的问题，进去一遍，出来一遍，尤其动态规划的场景居多。

非递归实现 #

很多递归实现很容易的代码，面试官会要求用非递归实现。解决办法通常是需要用栈的出栈和入栈来模拟递归过程。

常见题型 #

链表 #

206. 反转链表非常典型。

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    last := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}

21. 合并两个有序链表

var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

字符串 #

二叉树 #

226. 翻转二叉树

543. 二叉树的直径

var diameterOfBinaryTree = function(root) {
    let ret = 0
    let helper = function(root) {
        if (!root) {
            return 0
        }
        let l = helper(root.left)
        let r = helper(root.right)
        ret = Math.max(ret, l+r)
        return Math.max(l, r) + 1
    }
    helper(root)
    return ret
};