代码随想录一刷笔记_二叉树（上）

60+在408的算法考察难度和深度上还是收手了👍）

二叉树理论基础

二叉树的遍历方式
  • 深度优先遍历 => 栈
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 广度优先遍历 => 队列
    • 层次遍历

二叉树的定义

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {} // 构造函数，初始化对象
}

二叉树的前中后序遍历

使用非迭代方法遍历二叉树，前序遍历和中序遍历的过程有一定的区别，这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

tips：为什么只有前序和后序不能构造二叉树？

因为使用前序表示的是“中-左-右”，后序表示的是“左-右-中”，只有前序序列和后序序列的话，只能找到根节点是哪一个，但是不能确定其他节点处于根节点的左子树还是右子树。

然而，如果结合中序遍历的话，找到中间节点，就能一眼看出剩下的节点处于这个节点的左子树还是右子树。

中序遍历（迭代方法）

与前序与后序遍历（后序输出的结果就是前序的倒置）不同，中序遍历要访问的元素和要处理的元素会存在不一致的情况。

中序遍历是左中右，所以需要从根节点开始，一层层地向下访问，直到到达二叉树最左边的节点；然后再开始处理节点。

所以在使用迭代方法进行中序遍历的时候，需要借助一个指针cur判断当前处于哪一个步骤：

  1. 将当前节点及其向左路径的所有节点压入栈，此时cur指针指向的不是空节点；
  2. 弹出栈顶元素，处理这个元素并将其右节点压入栈，并进行处理右子树的步骤，此时cur指针指向的节点为空节点。
后序遍历（迭代方法）

由于直接实现后序遍历似乎是不行的，所以在这里可以采取逆向思维！（；´д｀）ゞ

后序遍历要实现的是左右中遍历二叉树，反过来的话就是中右左遍历。所以在这里采取了先进行中右左遍历，然后将结果数组翻转的做法。(⊙﹏⊙)

二叉树的统一迭代法

由于使用不同的遍历方法时，会存在访问节点和处理节点时间不一致的情况。故，可以采取将处理的节点放入栈的同时进行标记的方法！也就是在节点放入栈的同时放入一个空指针作为标记！

二叉树的层序遍历

二叉树的层序遍历（102）

  • 非递归方法

    tips: 遍历每一层的节点时，需要遍历队列中的现有元素。这里存在一个问题，遍历过程中，会将队列中的元素弹出，这样一来，队列的长度会发生变化。故，for循环的条件应为遍历前的队列长度（提前赋值的固定值）。

    1
    2
    3
    4
    5
    // 遍历当前队列q中的节点
    int size = q.size();
    ....
    // 循环条件中的size需要为固定值！
    for (int i = 0; i < size; i++){....}

  • 递归方法

    层序遍历的递归方法的函数如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void order(TreeNode *cur, vector<vector<int>> &result, int depth)
    {
        if (cur == nullptr) return;
        // 深度是从0开始计数的，所以每到遍历至新的一层时，都会添加一个新的内部向量来存储当前层节点的值。
        // 使用这样的技巧，result的层数和深度值是匹配的。
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
二叉树的最小深度（111）

  • 递归方法：需要在返回值里额外加一层判断，避免根节点一侧全为空的情况。

    1
    return min(left, right) < 1 ? max(left, right) + 1: min(left, right) + 1;

  • 非递归方法：最早遍历到的没有子树的节点就是最浅的深度所在的位置！

对称二叉树（101）

题目要求的是根节点两边是对称的，故可以考虑同时遍历根节点左右两边的节点，在这个过程中比较节点是否对称。

例如：遍历左子树时可以使用后序（左右中）的方法，遍历右子树的时候可以使用（右左中）的方法。这样一来，遍历得到的节点序列应当是相同的。

  • 递归方法

    递归可以简化为三个步骤：

    1. 确定递归函数的参数和返回值：在这个任务中，参数为左右子树节点，返回值为bool
    2. 确定终止条件：当出现两个节点不相等时
    3. 确定单层递归的逻辑：在单层递归中，需要同时比较两个节点的左右两个分支是否分别与对应节点的值相同。所以需要两个分支节点同时比较。
  • 迭代方法

    判断遍历到的左右子树中当前节点（nodel, noder）是否相等：

    1
    2
    3
    4
    // 两个节点都为空的情况
    if (!nodel && !noder) continue;
    // 两个节点存在一个为空节点或者两个节点数值不相同
    if (!nodel || !noder || (nodel->val != noder->val)) return false;

二叉树的最大深度（110）

深度和高度的区别

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）-> 使用后序遍历

二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始） -> 使用先序遍历

两个表示是反过来的

完全二叉树的节点个数（222）

完全二叉树有两种情况：

  1. 是一棵满二叉树
    • 如何判断：分别遍历根节点的左子树和右子树。其中，左子树向左遍历，右子树向右遍历；如果得到的两个深度相同，就是一棵完全二叉树。
  2. 最后一层叶子节点没有满
    • 分别递归左孩子和右孩子，递归到某一深度一定会有左孩子或者右孩子为完全二叉树！
    • image-20240924143020208

二叉树的所有路径（257）

你管这叫简单题？（；´д｀）ゞ

这一题涉及两件事情：
  1. 使用前序遍历，找到每一条路径；
  2. 将遍历的节点向上回溯到根节点，回退已遍历的路径再进入另一个路径。
递归方法

递归方法三部曲：

  1. 递归函数参数以及返回值

    需要传入根节点，记录当前路径的path，存放结果的result

    不需要返回值

  2. 确定递归终止条件

    当前的节点是叶子节点时

  3. 确定单层递归逻辑

    因为是要记录路径，所以使用前序遍历（优先处理父节点），将其放入path

    P.S. 回溯要和递归永远在一起，世界上最遥远的距离是你在花括号里！！！ 标准写法是，一个递归对应一个回溯，有多少个递归pg后面就跟着多少个回溯！！！

P.S. 代码精简方法：暗藏玄鸡（将回溯结合到参数调用中）

原来的方法中应用回溯，是因为原来的path路径使用数组存储的，我们需要将路径转化为需求的字符串形式。

到那时在这个写法里，path直接使用字符串存储，并且在递归调用过程中直接进行了操作，隐藏了回溯过程。执行完递归函数之后，path依旧是之前的数值（相当于回溯了）。

1
2
3
// 然后处理左右两个节点
if (node->left)	traversal(node->left, path + "->", result);
if (node->right) traversal(node->right, path + "->", result);
迭代方法

使用迭代方法解决这一题也可以分为两步走：

  1. 使用前序遍历迭代遍历二叉树

  2. 记录迭代过程中的路径

    这里额外使用一个栈存放路径（故里面存放的类型为string）。

    每当遍历到一个节点时，往这个栈中存放根节点到这个子节点的整个路径；直到遍历到叶子节点时，将整条路径赋给result。👍👍👍

左叶子之和（404）

这一题初印象感觉还是得用层序遍历，将每一层的左节点进行一个累加，然后输出结果减去根节点的值即可。

但是（强调！），抓狂的是，因为这棵树不一定是一棵完全二叉树，所以会存在这一层可能不存在第一个左节点的情况（这一层中第一个节点可能是右节点）！

考虑过使用第一个节点在这一层中序号是否为奇数来判断，但是！又是但是！层序遍历的过程中不会将空节点存入队列。

看了解答后，似乎对题目理解也有了点误区，他要求的是所有属于其父节点的左子树的叶子结点的值的和。

正解！：这一题并不复杂，只要在遍历过程中判断一下当前节点的左子树（如果存在的话）是否为叶子节点，将这个叶子节点值加入求和即可。

找树左下角的值（513）

迭代方法

这一题使用迭代的方法很简单，只需使用层序遍历，记录每一层的第一个节点值即可。

递归方法

可以拆解为两步：① 找到最后一层的节点；② 找到最左边的值。

所以在迭代的过程中，需要保证左子树左节点是优先被遍历的，故前中后序三种遍历顺序均可。

路径总和（112）& 路径总和（113）

这两题放一起，主要是说明什么时候需要返回值。

当不需要遍历整个二叉树时，考虑有返回值。

对于递归函数来说，

  • 如果没有返回值，就说明需要遍历整棵二叉树

  • 如果有返回值，需要进行分类讨论：

    如果需要搜索一条边，递归函数返回值不为空的情况下，立刻返回；

    如果搜索整棵树，需要使用一个变量left，right接住返回值，后面还有left、right的逻辑处理，即后序遍历中对于中间节点的处理（回溯）。

    • 搜索一条边的写法

      1
      2
      if (递归函数(root->left)) return;
      if (递归函数(root->right)) return;

    • 搜索整棵树的写法

      1
      2
      3
      left = 递归函数(root->left);
      right = 递归函数(root->right);
      left & right 的处理逻辑

在112中，只需要找到一个总和为 targetNum 的路径即可，找到后就可以返回；而在 113 中，需要找到所有符合要求的路径，所以考虑没有返回值，遍历所有路径。

P.S. 对过程的一些简化

路径总和（112）

  1. 传入的参数

    可以只考虑传入两个参数：二叉树节点和总和值。在遍历二叉树时，只需要在总和值的基础上进行计算即可，最后是遍历到叶子节点的时候判断这个值是否为0！

  2. 使用迭代方法时，需要一个额外的值记录当前路径的总和。考虑使用记录当前节点路径上的总和的方法，使用一个pair结构存放。

从中序与后序遍历序列构造二叉树（106）

这是遇到的第一个有关构造二叉树的题目！

人工的方法还是很好想的， 但是如何进行编程没有什么头绪。

使用递归的方法对后序数组和中序数组进行遍历：
  1. 如果数组大小为0，说明已经完成力；
  2. 若不为空，那么取后序数组最后一个元素作为当前子树的根节点；
  3. 找到这个元素在中序数组的位置，作为切割点；
  4. 切割中序数组，切成中序左数组和中序右数组；
  5. 切割后序数组，切成后序左数组和后序右数组；
  6. 递归处理左区间和右区间。

P.S. 在C++中使用 std::vector 的范围构造函数时，遵循的是**左闭右开**原则。

合并二叉树（617）

题目是挺好理解的，将两棵二叉树对应节点的值合并即可。

P.S. 写程序时存在的问题

在遍历节点时原来是这样写的（以节点的左子树为例）：

在满足“node1的左节点不存在 && node2的左节点存在”的情况时，执行赋值操作后多写了一个return，导致后面的对两棵树右节点的判断没有执行！

故，应该把return放到递归操作的最后在执行一下。

1
2
3
4
5
6
if (node1 && node2 && node1->left && node2->left) traversal(node1->left, node2->left);
else if (!node1->left && node2->left)
{
    node1->left = node2->left;
    return;
}

二叉搜索树中的搜索（700）

迭代方法

因为，二叉搜索树是一棵有序的树！所以在面对遍历这棵树中有无节点与给出的值相同的需求时，不需要借助额外的数据结构，只要一条路走到黑（遍历到空节点即可）！！！

验证二叉搜索树（98）

这一题主要是在二叉搜索树的定义上还要折腾一下，不仅要考虑当前节点和他的子节点们，还要考虑整一棵子树和父节点等的关系。

那么该如何验证呢？只要使用中序遍历的方法，增加遍历到的当前节点满足数值比前一个节点数值大的条件就可以了！

二叉搜索树中的众数（501）

思路1：①中序遍历BST，将节点数值存入哈希表中；②遍历哈希表，找到出现最高的频率值；③在哈希表中找到对应的众数输出。（不用卡死BST，普通二叉树也适用的方法！）

思路2：在遍历的过程中，对出现过的数值计数并放入result中，如果出现了频率更高的数，将result清空并填入这个新的数值！！！！

P.S.
  1. vector<pair<int, int>> vec(map.begin(), map.end());

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

       

       用法：一种**语法糖**，提供了一种简洁的方式来初始化一个`std::vector`对象，而不需要显式地逐个复制元素。

       将一个`std::map`或`std::unordered_map`的元素复制到一个`std::vector`的`std::pair<int, int>`类型的容器中。

    2. `sort`函数的两个重载形式

       - 不带自定义比较函数的重载

         默认使用`<`来比较元素，对给定范围内的元素进行升序排序。

         ```c++
         sort(result.begin(), result.end());
    

- 带自定义比较函数的重载

  `sort()`函数接受一个自定义比较函数`comp`，允许自定义排序的逻辑。

  在这一个问题中是这样定义**根据map中的值**进行排序的：

  
    1
    2
    3
    bool cmp(const pair<int, int>& a, const pair<int, int>& b)
        return a.second > b.second;
    sort(map.begin(), map.end(), cmp)
    

  **定义比较函数**时，建议使用**常量引用**作为参数类型，这样可以避免不必要的拷贝，提高效率!!!
LeetCode > 代码随想录
#Notes #LeetCode #Data structure #Algorithm #C++
代码随想录一刷笔记_二叉树（上）
http://example.com/2024/09/20/code-6-binary tree-1/
作者
Poivre
发布于
2024年9月20日
许可协议