二叉树专题训练一

3 minute read

4/26

T111 二叉树的最小深度

这一题我觉得比上一题难，难在如何确定“截屏面”——选定一个瞬间，假设返回值都能求到，再根据不同情况进行处理。我认为这类题目直接看答案觉得简单、自己写难的重要原因是有时截屏面能符合逻辑，但深入到具体执行时，每次返回值和截止条件可能会出现错误，这需要通过实例自己规避好边界问题和特殊情况。

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

T104 二叉树的最大深度

经典深度优先题目，本质是求根节点的最大高度

class Solution {
public:
    int getdepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftdepth = getdepth(node->left);       // 左
        int rightdepth = getdepth(node->right);     // 右
        int depth = 1 + max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getdepth(root);
    }
};

4/25

T01 对称二叉树

1、不是左右节点分别判断，当心
2、这道题对空节点需要格外当心，前期先仔细排除
3、迭代法待研究

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

T226 翻转二叉树

1、这道题几种递归都可以，例如：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};

然而，中序遍历会把某些节点的左右子节点翻转两次，应当小心（层序遍历依旧可以）

2、迭代法，不如递归那么好理解，但可以AC：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

4/24

T02 二叉树的层序遍历

几个关键点：
1、注释里写的size问题，很容易出错，需要固定下来
2、之所以每次都能抓住一层节点赋值，本质是上一个循环中上一层所有相邻子节点的总数目确定了，刚好遍历完，不会触及下下层子节点
3、数据结构：队列

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

【二叉树知识点复习——递归遍历】

前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

中序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

注：汇编层面的栈知识点待复习迭代法待断点运行理解+创新

4/23

T347 前K个高频元素【堆方法补全理解】

今天把逻辑彻底理顺，关键如下：

1、为何用“小顶堆”而不是大顶堆
目标是保留“前K大”，但我们不需要完整排序。
核心思想：只维护一个大小为K的集合，让这个集合始终是“当前最优的K个”。

若用大顶堆：堆顶是最大值，但我们无法快速淘汰“最小的那个”，不符合需求。
若用小顶堆：堆顶是当前K个里“最小的那个”，一旦来了更大的，就可以直接替换掉它。
本质：维护的是一个“动态门槛”，而这个门槛就是堆顶。

2、为什么堆大小只需要K
遍历频率数组时：
情况一：堆未满 → 直接加入
情况二：堆已满：
若当前频率 <= 堆顶 → 无资格进入
若当前频率 > 堆顶 → 替换堆顶

关键结论：
被淘汰的元素不可能进入最终答案

证明：假设某元素被淘汰，说明它比当前堆里某个元素小，而堆里这K个元素已经是“当前最优K个”之后即使有新元素，也只会替换更小的，所以它永远没有机会再回来

3、时间复杂度分析
建map：O(n)
遍历map：O(n log k)

关键：
log k « log n
因此整体优于排序：O(n log n)

4/22

【Next数组数学推导原理证明】

看完代码讲解后没有彻底理解清楚为何这么做，不满足于记忆代码，故找到严格证明逻辑并彻底理解。关键如下：

1、用递推的逻辑来理解
很多视频一上来就初始化、进入循环，没有讲清楚为何这么设置循环，只展示运行成果。我找到一个网课视频B站链接，没有听讲，盯着里面的PPT搞懂了。
我们先假设存在图片中这个东西，再分别证明等于和不等于的情况下代码逻辑的合理性。

2、等于时：很简单，前面已经是最长相等，后面再分别连接一个字符，自然++

3、不等时：Next数组灵魂所在。
既然不等，我们的最长相等就只能从去掉最新字符的一整个前端区域里寻找，要找就找最长的。我们把左边紫色的前后相等缀称作AB，右边紫色的称作CD。假设我们找的是一段长于0….k-1中最长相等的区域A’，那么，由于A’不等于B’（左侧紫色从尾端往前数和A’同样长度的区域），对应右侧紫色区域中的C’也不等于D’，由于A’=C’，B’=D’，故A’=C’!=D’。A’、D’既然不相等，自然无法成为总区域的最长相等。
综上，必须找到A’=B’的，而又要最长，0…..k-1区域的最长相等便势在必行。
现在，我们已经找到当前情况下最佳的解，再尝试匹配新字符。假如可以，采纳，进入下一层循环；假如不行，我们又回到了原先的情况，递归，继续找A’新小紫色区域中的最长相等，也就是while代码中的跳跃逻辑。
注意：这里有一个容易陷入的误区——为何不直接找A’-1的区域进行比对，难道不能每次减少一位，直接跳跃不会错过更优解么？
答案：不可能。因为假如A’= 1 2 3 4 5，D’= 1 2 3 4 5，A’-1后变成了1 2 3 4，D’-1后变成了2 3 4 5【而非1 2 3 4，后缀是以末尾为标准前推的】，两者就不存在任何必要的相等关系了，得重新根据前面那套ABCD的推理来寻找最佳项，
故，持续递归直到来到零处或符合要求。
证毕。

4/21

T347 前K个高频元素

非进阶写法很简单（nlong复杂度）：
//直接遍历数组，建立二维数组，统计每个整数出现次数
//快速排序，取前K个最大值

复习一些我忘掉的语法知识：

1、auto让编译器自动推断类型。
for (auto& p : mp)

2、sort(vec.begin(), vec.end(), …)表示对整个 vec 排序；pair<int,int>& a, pair<int,int>& b
表示每次拿两个元素 a 和 b 来比较。

例如：
a = (1,3)
b = (2,2)
return a.second > b.second;

意思是：如果 a 的频率比 b 大，就认为 a 应该排在前面

sort(vec.begin(), vec.end(), { return a.second > b.second; });

进阶写法一：桶排序，空间换时间

这个我不是很认可，我觉得不优雅，且空间上太浪费了。

进阶写法二：小顶堆

该知识点和大顶堆一起放入明日学习，属于heap层面，已不在栈和队列覆盖范围

T239 滑动窗口最大值

这道题经典中的经典，核心是单调队列。和传统队列不同，这里的队列存储的不是数值而是下标，但所有元素从队头至队尾按照数值从高到低递减。

时间复杂度：O(n)

结合代码说明几个关键点：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq; // 存下标
        vector<int> res;

        for (int i = 0; i < nums.size(); i++) {
            // 1. 保持单调递减（从大到小）
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            // 2. 移除窗口外元素
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            // 3. 记录结果
            if (i >= k - 1) {
                res.push_back(nums[dq.front()]);
            }
        }
        return res;
    }
};

这一步我一开始有疑问——一下子pop这么多，万一下一个滑动窗口里pop掉的内容是潜在的最大值怎么办？经过简洁的数学证明，我找到原因：

例如，6 5 4 3 2 1 100 0 0 0 0
“100”会把前面所有值吞掉，但由于“100”是最新触碰的元素，即下标最大的已接触元素，而它又大于所有之前pop掉的值，因此对于新的滑动窗口来说，只要之前pop掉的元素下标范围还在窗口内，“100”的下标范围就一定在滑动窗口内，也就依旧能干掉pop掉的那些值，故pop掉的值无机会成为最大值，可直接丢弃。

注：将上面的nums[dq.back()] < nums[i]改为nums[dq.back()] <= nums[i]一样可以通过测试，因为假设相等，新来的可以代替之前的相等值（窗口已覆盖到新来的下标），而在未覆盖到新来者之时，新来者并未对它们产生影响。

补充知识点：
1、C++中deque是stack和queue默认的底层实现容器（也可以替换为 vector 或 list 等符合接口要求的容器）
2、deque是可以两边扩展的，push_front() → 头部插入 push_back() → 尾部插入，都是O(1)复杂度
3、deque里元素并不是严格的连续分布——deque 的内存是分段连续的（segmented storage），而不是像 vector 那样的单块连续内存

4/20

T150 逆波兰表达式

就是后缀表达式运算，使用栈，核心：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

拓展：中缀、前缀表达式，在进行到二叉树相关知识点时一并复习

T1047 删除字符串中的所有相邻重复项

简单，栈即可。栈的特点之一就是能方便让栈顶元素与当前元素比较，遍历时很容易找到重复项。

虽然该题很简单，但我是看到专题标签（栈与队列）才一下子想到解法的。如果没有这个专题的提示加成，或许不会这么容易。这一点要注意，未来面试时是不会有这种提示的。

Share on

X Facebook LinkedIn Bluesky