36-50-二叉树

LeetCode 热题 100

文章目录

• LeetCode 热题 100
• 二叉树
• • 36. 简单-二叉树的中序遍历
  • 37. 简单-二叉树的最大深度
  • 38. 简单-翻转二叉树
  • 39. 简单-对称二叉树
  • 40. 简单-二叉树的直径
  • 41. 中等-二叉树的层序遍历
  • 42. 简单-将有序数组转换成二叉搜索树
  • 43. 中等-验证二叉搜索树
  • 44. 中等-二叉搜索树中第K小的元素
  • 45. 中等-二叉树的右视图
  • 46. 中等-二叉树展开为链表
  • 47. 中等-从前序与中序遍历序列构造二叉树
  • 48. 中等-路经总和III
  • 49. 中等-二叉树的最近公共祖先
  • 50. 困难-二叉树的最大路径和

本文存储我刷题的笔记。

二叉树

36. 简单-二叉树的中序遍历

我的思路：递归

• 思路：中序遍历是“左根右”。那么就不断按照这个顺序递归就好了。
• 时间复杂度：$O(n)$，其中 $n$ 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
• 空间复杂度：$O(n)$。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 $O(n)$ 的级别。
• 时间0ms(100.00%)，内存8.59MB(30.14%)。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:// 自定义递归函数void inorder(TreeNode* root, vector<int>& res) {// 只有空，才返回if (!root) {return;}inorder(root->left, res); // 左侧res.push_back(root->val); // 根inorder(root->right, res);// 右侧}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}};

官方思路二：迭代

• 思路：递归时隐式的使用栈来存储函数，要使用“迭代”完成此题，只需要将显式的定义这个栈即可。
• 时间复杂度：$O(n)$，其中 $n$ 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
• 空间复杂度：$O(n)$。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 $O(n)$ 的级别。
• 时间0ms(100.00%)，内存8.64MB(22.12%)。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;// 结果stack<TreeNode*> stk; // 显式的定义栈while (root != nullptr || !stk.empty()) {// 一直深入到左侧最深的节点，并不断压栈while (root != nullptr) {stk.push(root);root = root->left;}// 弹出左侧第一个最深的根节点root = stk.top();stk.pop();// 输出当前的根节点res.push_back(root->val);// 去当前根节点的右侧压栈root = root->right;}return res;}};

官方思路三：Morris中序遍历

• 思路：本方法通过将每个根节点 $x$ 的左子树的最右侧节点指向自己，可将非递归的中序遍历空间复杂度降为 $O(1)$。算法步骤如下：

1. 如果 $x$ 无左孩子，先将 $x$ 的值加入答案数组，再访问 $x$ 的右孩子，即 $x=x.\text{right}$。
2. 如果 $x$ 有左孩子，则找到 $x$ 左子树上最右的节点（即左子树中序遍历的最后一个节点，$x$ 在中序遍历中的前驱节点），我们记为 $\text{predecessor}$。根据 $\text{predecessor}$ 的右孩子是否为空，进行如下操作。

• 如果 $\text{predecessor}$ 的右孩子为空，则将其右孩子指向 $x$，然后访问 $x$ 的左孩子，即 $x=x.\text{left}$。
• 如果 $\text{predecessor}$ 的右孩子不为空，则此时其右孩子指向 $x$，说明我们已经遍历完 $x$ 的左子树，我们将 $\text{predecessor}$ 的右孩子置空，将 $x$ 的值加入答案数组，然后访问 $x$ 的右孩子，即 $x=x.\text{right}$。

3. 重复上述操作，直至访问完整棵树。

• 时间4ms(39.41%)，内存8.58MB(32.18%)。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;TreeNode *predecessor = nullptr;while (root != nullptr) {if (root->left != nullptr) {// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止predecessor = root->left;while (predecessor->right != nullptr && predecessor->right != root) {predecessor = predecessor->right;}// 让 predecessor 的右指针指向 root，继续遍历左子树if (predecessor->right == nullptr) {predecessor->right = root;root = root->left;}// 说明左子树已经访问完了，我们需要断开链接else {res.push_back(root->val);predecessor->right = nullptr;root = root->right;}}// 如果没有左孩子，则直接访问右孩子else {res.push_back(root->val);root = root->right;}}return res;}};

37. 简单-二叉树的最大深度

我的思路

• 思路：其实就是“中序遍历”时，栈的最大深度。

• 时间” />

  官方思路一：深度优先搜索

  • 思路：使用 递归，若左子树和右子树的最大深度 $l$ 和 $r$，那么该二叉树的最大深度即为 $max(l,r)+1$。
  • 时间复杂度：$O(n)$，其中 $n$ 为二叉树节点的个数。每个节点在递归中只被遍历一次。
  • 空间复杂度：$O(\text{height})$，其中 $\text{height}$ 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。
  • 时间0ms(100.00%)，内存18.79MB(25.96%)。

  /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:int maxDepth(TreeNode* root) {if(root == nullptr){return 0;}return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;}};

  官方思路二：广度优先搜索

  • 思路：每次都完整的遍历一层，使用队列 std::queue来(从前面)弹出当前层数据、(从后面)压入下一层的数据，最后看看能达到几层。
  • 时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
  • 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 $O(n)$。
  • 时间8ms(72.22%)，内存18.96MB(5.68%)。

  /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:int maxDepth(TreeNode* root) {// 排除特殊情况：空二叉树if (root == nullptr) return 0;// 广度优先搜索int ans = 0; // 层数queue<TreeNode*> Q; // 暂存每层Q.push(root); // 第一层while (!Q.empty()) {int sz = Q.size(); // 当前层的节点数// 将当前层全部替换成下一层的数据while (sz > 0) {TreeNode* node = Q.front();Q.pop(); // 弹出当前节点if (node->left) Q.push(node->left); // 压入左节点if (node->right) Q.push(node->right); // 压入右节点sz -= 1;}// 更新层数ans += 1;} return ans;}};

  38. 简单-翻转二叉树

  

  我的思路：递归

  • 思路：递归，从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 $\text{root}$ 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 $\text{root}$ 为根节点的整棵子树的翻转。

  • 时间复杂度：$O(N)$，其中 $N$ 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

  • 空间复杂度：$O(N)$。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 $O(\log N)$。而在最坏情况下，树形成链状，空间复杂度为 $O(N)$。

  • 时间4ms(46.88%)，内存9.91MB(16.11%)。

  /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:TreeNode* invertTree(TreeNode* root) {if (root == nullptr) {return nullptr;}TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;}};

  39. 简单-对称二叉树

  

  我的思路：递归

  • 思路：递归，通过「同步移动」两个指针的方法来遍历这棵树，$p$ 指针和 $q$ 指针一开始都指向这棵树的根，随后 $p$ 右移时，$q$ 左移，$p$ 左移时，$q$ 右移。每次检查当前 $p$ 和 $q$ 节点的值是否相等，如果相等再判断左右子树是否对称。

  • 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 $O(n)$。
    空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 $n$，故渐进空间复杂度为 $O(n)$。

  • 时间4ms(77.45%)，内存16.24MB(68.78%)。

  /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:// 自定义递归函数bool check(TreeNode *p, TreeNode *q) {// 情况一：两者全为空if (!p && !q) return true;// 情况二：两者只有一个空if (!p || !q) return false;// 其他情况：当前相同 且 p左子树和q右子树相同 且 p右子树和q左子树相同return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);}bool isSymmetric(TreeNode* root) {return check(root, root);}};

  官方思路二：迭代

  • 思路：使用 队列std::queue，将递归方法改成迭代形式。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
  • 时间复杂度：$O(n)$，同「方法一」。
    空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 $n$ 个点，故渐进空间复杂度为 $O(n)$。
  • 时间4ms(77.45%)，内存16.60MB(11.64%)。

  /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:// 自定义函数bool check(TreeNode *u, TreeNode *v) {queue <TreeNode*> q;q.push(u); q.push(v);// 每次比较两个节点，一层一层的比较while (!q.empty()) {// 弹出两个节点u = q.front(); q.pop();v = q.front(); q.pop();// 两节点都为空if (!u && !v) continue;// 两节点不一样if ((!u || !v) || (u->val != v->val)) return false;// 两节点都有意义时，压入镜像的两侧q.push(u->left); q.push(v->right);q.push(u->right); q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}};

  40. 简单-二叉树的直径

  

  我的思路

  • 思路：没有想法…

  • 时间” />

    官方思路一：深度优先搜索

    • 思路：使用 递归，每次都计算以当前节点为起点的子树的最长路径的节点数。任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。于是经过当前节点的最多节点路径 = 左子树为起点的最多节点 + 右子树为起点的最多节点 + 1。后面求“直径”时再减去1即可。
    • 时间复杂度：$O(N)$，其中 $N$ 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
    • 空间复杂度：$O(Height)$，其中 $Height$ 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 $O(Height)$。
    • 时间8ms(78.94%)，内存20.15MB(29.53%)。

    /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {// 全局变量-最多节点数int ans;// 自定义递归函数：求解以当前节点为起点的子树的最长节点数int depth(TreeNode* rt){if (rt == NULL) {return 0; // 访问到空节点了，返回0}int L = depth(rt->left);// 左儿子为根的子树的最长节点数int R = depth(rt->right); // 右儿子为根的子树的最长节点数// 更新全局变量ans = max(ans, L + R + 1);// 计算d_node即L+R+1 并更新ans// 返回该节点为根的子树的深度return max(L, R) + 1;}public:int diameterOfBinaryTree(TreeNode* root) {ans = 1;depth(root);// 找出最长路径的节点数return ans - 1; // 最后减一}};

    41. 中等-二叉树的层序遍历

    42. 简单-将有序数组转换成二叉搜索树

    

    我的思路

    • 思路：根据数组长度计算层数，然后一层一层放。好像也不行，本质上是考察如何遍历二叉树。

    • 时间” />

      官方思路一：中序遍历，总是选择中间位置左边的数字作为根节点

      • 思路：通过递归的方式，每次选取中间位置左边的数字 mid= ⌊L + R2⌋{\rm mid} = \lfloor \frac{L + R}{2} \rfloormid=⌊2L+R​⌋ 作为根节点，然后将 $[L,\text{mid}-1]$ 传给左节点去平衡构造、将 $[\text{mid}+1，R]$ 传给右节点去平衡构造。
      • 时间复杂度：$O(n)$，其中 $n$ 是数组的长度。每个数字只访问一次。
      • 空间复杂度：$O(\log n)$，其中 $n$ 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 $O(\log n)$。
      • 时间8ms(92.79%)，内存21.19MB(46.48%)。

      /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:TreeNode* sortedArrayToBST(vector<int>& nums) {return helper(nums, 0, nums.size() - 1);}// 递归函数：不断选取中间左侧作为根节点TreeNode* helper(vector<int>& nums, int left, int right) {// 区间长度小于1，则可以进行返回if (left > right) {return nullptr;}// 选取根节点int mid = (left + right) / 2; // 中间位置左边的数字TreeNode* root = new TreeNode(nums[mid]);// 左右两侧递归创建root->left = helper(nums, left, mid - 1);root->right = helper(nums, mid + 1, right);return root;}};

      官方思路二：中序遍历，总是选择中间位置右边的数字作为根节点

      • 思路：方法同上，只不过选取中间位置右侧作为根节点。

      • 时间8ms(92.79%)，内存21.25MB(34.59%)。

      /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:TreeNode* sortedArrayToBST(vector<int>& nums) {return helper(nums, 0, nums.size() - 1);}// 递归函数：不断选取中间左侧作为根节点TreeNode* helper(vector<int>& nums, int left, int right) {// 区间长度小于1，则可以进行返回if (left > right) {return nullptr;}// 选取根节点int mid = (left + right + 1) / 2; // 中间位置右边的数字TreeNode* root = new TreeNode(nums[mid]);// 左右两侧递归创建root->left = helper(nums, left, mid - 1);root->right = helper(nums, mid + 1, right);return root;}};

      官方思路三：中序遍历，选择任意一个中间位置数字作为根节点

      • 思路：方法同上，只不过选取中间位置任意侧作为根节点。

      • 时间16ms(38.38%)，内存21.15MB(55.69%)。

      /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:TreeNode* sortedArrayToBST(vector<int>& nums) {return helper(nums, 0, nums.size() - 1);}// 递归函数：不断选取中间左侧作为根节点TreeNode* helper(vector<int>& nums, int left, int right) {// 区间长度小于1，则可以进行返回if (left > right) {return nullptr;}// 选取根节点int mid = (left + right + rand() % 2) / 2;; // 中间任意一个数字TreeNode* root = new TreeNode(nums[mid]);// 左右两侧递归创建root->left = helper(nums, left, mid - 1);root->right = helper(nums, mid + 1, right);return root;}};

      43. 中等-验证二叉搜索树

      44. 中等-二叉搜索树中第K小的元素

      45. 中等-二叉树的右视图

      46. 中等-二叉树展开为链表

      47. 中等-从前序与中序遍历序列构造二叉树

      48. 中等-路经总和III

      49. 中等-二叉树的最近公共祖先

      50. 困难-二叉树的最大路径和

      

      我的思路

      • 思路：

      • 时间” />

        官方思路：

        • 思路：

        • 时间??ms(??%)，内存??MB(??%)。