思维培养 #
理解递归的关键首先还是弄清楚二叉树的先序遍历、中序遍历和后序遍历的递归实现。任何递归可以说都处在这个模型中。
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
}
https://labuladong.github.io/algo/2/17/17/
合并有序链表 #
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;
}
};