LeetCode 刷题指南：二叉树框架与算法核心笔记

为什么要学算法？

想要进入大厂，算法必不可少。尤其是字节跳动等公司，面试最大的特点就是爱考算法题。你随便翻几篇面经就会发现，考的算法题一般都是 LeetCode 原题，只是有的时候你没刷过，不知道那道题是 LeetCode 上的原题。

算法刷题指南

首先要明确的是，数据结构是工具，算法是通过合适的工具解决特定问题的方法。也就是说，学习算法之前，最起码得了解那些常用的数据结构，了解它们的特性和缺陷。

那么该如何在 LeetCode 刷题呢？直接说具体的建议：先刷二叉树，先刷二叉树，先刷二叉树！

这是我这刷题一年的亲身体会。刷二叉树看到题目没思路？根据很多读者的问题，其实大家不是没思路，只是没有理解我们说的「框架」是什么。不要小看这几行代码，几乎所有二叉树的题目都是一套这个框架就出来了。

void traverse(TreeNode* root) {
    // 前序遍历
    traverse(root->left);
    // 中序遍历
    traverse(root->right);
    // 后序遍历
}

比如我随便拿几道题的解法出来，不用管具体的代码逻辑，只要看看框架在其中是如何发挥作用就行。

LeetCode 124 题，难度 Hard，让你求二叉树中最大路径和，主要代码如下：

int ans = INT_MIN;
int oneSideMax(TreeNode* root) {
    if (root == nullptr) return 0; 
    int left = max(0, oneSideMax(root->left));
    int right = max(0, oneSideMax(root->right)); 
    ans = max(ans, left + right + root->val);
    return max(left, right) + root->val;
}

你看，这就是个后序遍历嘛。

LeetCode 105 题，难度 Medium，让你根据前序遍历和中序遍历的结果还原一棵二叉树，很经典的问题吧，主要代码如下：

TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder,  inStart,  inEnd, Map<Integer, Integer> inMap) {
    (preStart > preEnd || inStart > inEnd)  ; 
        (preorder[preStart]); 
       inMap.get(root.val);
       inRoot - inStart;
    root.left = buildTree(preorder, preStart + , preStart + numsLeft, inorder, inStart, inRoot - , inMap);
    root.right = buildTree(preorder, preStart + numsLeft + , preEnd, inRoot + , inEnd, inMap); 
     root; 
}