深圳幻海软件技术有限公司 欢迎您！
更多

C/C++每日一练(20230326) 二叉树专场（3）

2023-04-12

node root nums
目录1.二叉树的前序遍历  🌟🌟2.二叉树的最大深度  🌟3.有序数组转换为二叉搜索树  🌟🌟🌟每日一练刷题专栏 🌟Golang每日一练专栏Python每日一练专栏C/C++每日一练专栏Java每日一练专栏1.二叉树

目录

1. 二叉树的前序遍历  🌟🌟

2. 二叉树的最大深度  🌟

3. 有序数组转换为二叉搜索树  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

出处：

https://edu.csdn.net/practice/23819517

代码： 递归算法

  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. struct TreeNode
  7. {
  8.     int val;
  9.     TreeNode *left, *right;
  10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  11. };
  12.  
  13. class Solution
  14. {
  15. private:
  16.     void rec(TreeNode *root, vector<int> &ret)
  17.     {
  18.         if (root != nullptr)
  19.         {
  20.             ret.push_back(root->val);
  21.             rec(root->right, ret);
  22.             rec(root->left, ret);
  23.         }
  24.     }
  25. public:
  26.     vector<int> postorderTraversal(TreeNode *root)
  27.     {
  28.         vector<int> ret;
  29.         rec(root, ret);
  30.         return ret;
  31.     }
  32. };
  33.  
  34. string Vector2String(vector<int> vect) {
  35.     stringstream ss;
  36. ss << "[";
  37.     for (size_t i = 0; i < vect.size(); i++)
  38. {
  39.         ss << to_string(vect[i]);
  40.         ss << (i < vect.size() - 1 ? "," : "]");
  41.     }
  42.     return ss.str();
  43. }
  44.  
  45. int main()
  46. {
  47.     TreeNode *root = new TreeNode(1);
  48.     root->right = new TreeNode(2);
  49.     root->right->left = new TreeNode(3);
  50.     Solution s;
  51. cout << Vector2String(s.postorderTraversal(root)) << endl;
  52.     
  53.     return 0;
  54. }

输出：

[2,1,3]

进阶： 迭代算法

  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. #include <queue>
  5. #include <stack>
  6. #define null INT_MIN
  7. using namespace std;
  8.  
  9. struct TreeNode
  10. {
  11.     int val;
  12.     TreeNode *left, *right;
  13.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  14. };
  15.  
  16. TreeNode* buildTree(vector<int>& nums)
  17. {
  18.     if (nums.empty()) return nullptr;
  19. TreeNode *root = new TreeNode(nums.front());
  20.     queue<TreeNode*> q;
  21.     q.push(root);
  22.     int i = 1;
  23.     while(!q.empty() && i < nums.size())
  24.     {
  25.         TreeNode *cur = q.front();
  26.         q.pop();
  27.         if(i < nums.size() && nums[i] != null)
  28.         {
  29.             cur->left = new TreeNode(nums[i]);
  30.             q.push(cur->left);
  31.         }
  32.         i++;
  33.         if(i < nums.size() && nums[i] != null)
  34.         {
  35.             cur->right = new TreeNode(nums[i]);
  36.             q.push(cur->right);
  37.         }
  38.         i++;
  39.     }
  40.     return root;
  41. }
  42.  
  43. void preorderPrint(TreeNode* root) {
  44.     stack<TreeNode*> st;
  45.     st.push(root);
  46.     while (!st.empty()) {
  47.         TreeNode* node = st.top();
  48.         st.pop();
  49.         if (node != nullptr) {
  50.             cout << node->val << " ";
  51.             st.push(node->right);
  52.             st.push(node->left);
  53.         }
  54.     }
  55.     cout << endl;
  56. }
  57.  
  58. void preorderPrint2(TreeNode* root) {
  59.     stack<TreeNode*> st;
  60.     TreeNode* node = root;
  61.     while (node != nullptr || !st.empty()) {
  62.         while (node != nullptr) {
  63.             cout << node->val << " ";
  64.             st.push(node);
  65.             node = node->left;
  66.         }
  67.         node = st.top();
  68.         st.pop();
  69.         node = node->right;
  70.     }
  71.     cout << endl;
  72. }
  73.  
  74. vector<int> preorderTraversal(TreeNode* root) {
  75.     vector<int> res;
  76.     stack<TreeNode*> st;
  77.     st.push(root);
  78.     while (!st.empty()) {
  79.         TreeNode* node = st.top();
  80.         st.pop();
  81.         if (node != nullptr) {
  82.             res.push_back(node->val);
  83.             st.push(node->right);
  84.             st.push(node->left);
  85.         }
  86.     }
  87.     return res;
  88. }
  89.  
  90. vector<int> preorderTraversal2(TreeNode* root) {
  91.     vector<int> res;
  92.     stack<TreeNode*> st;
  93.     TreeNode* node = root;
  94.     while (node != nullptr || !st.empty()) {
  95.         while (node != nullptr) {
  96.             res.push_back(node->val);
  97.             st.push(node);
  98.             node = node->left;
  99.         }
  100.         node = st.top();
  101.         st.pop();
  102.         node = node->right;
  103.     }
  104.     return res;
  105. }
  106.  
  107. string vectorToString(vector<int> vect) {
  108.     stringstream ss;
  109. ss << "[";
  110.     for (size_t i = 0; i < vect.size(); i++)
  111. {
  112.         ss << (vect[i] == null ? "null" : to_string(vect[i]));
  113.         ss << (i < vect.size() - 1 ? "," : "]");
  114.     }
  115.     return ss.str();
  116. }
  117.  
  118. int main()
  119. {
  120. vector<int> nums = {1,null,2,3};
  121.     TreeNode *root = buildTree(nums);
  122.     preorderPrint(root);
  123.     preorderPrint2(root);
  124. cout << vectorToString(preorderTraversal(root)) << endl;
  125. cout << vectorToString(preorderTraversal2(root)) << endl;
  126.     
  127. nums = {3,9,20,null,null,15,7};
  128.     root = buildTree(nums);
  129.     preorderPrint(root);
  130.     preorderPrint2(root);
  131. cout << vectorToString(preorderTraversal(root)) << endl;
  132.  cout << vectorToString(preorderTraversal2(root)) << endl;
  133.     
  134. nums = {1,2,3,4,5,6,7};
  135.     root = buildTree(nums);
  136.     preorderPrint(root);
  137.     preorderPrint2(root);
  138. cout << vectorToString(preorderTraversal(root)) << endl;
  139. cout << vectorToString(preorderTraversal2(root)) << endl;
  140.     
  141.     return 0;
  142. }

输出：

1 2 3
1 2 3
[1,2,3]
[1,2,3]
3 9 20 15 7
3 9 20 15 7
[3,9,20,15,7]
[3,9,20,15,7]
1 2 4 5 3 6 7
1 2 4 5 3 6 7
[1,2,4,5,3,6,7]
[1,2,4,5,3,6,7]

中序后序对比：

  1. //中序遍历
  2. void inorder(TreeNode* root) {
  3.     stack<TreeNode*> st;
  4.     TreeNode* node = root;
  5.     while (!st.empty() || node != nullptr) {
  6.         while (node != nullptr) {
  7.             st.push(node);
  8.             node = node->left;
  9.         }
  10.         node = st.top();
  11.         st.pop();
  12.         cout << node->val << " ";
  13.         node = node->right;
  14.     }
  15. }
  16.  
  17. //后序遍历
  18. void postorder(TreeNode* root) {
  19.     stack<TreeNode*> st;
  20.     TreeNode* node = root;
  21.     TreeNode* last = nullptr;
  22.     while (!st.empty() || node != nullptr) {
  23.         while (node != nullptr) {
  24.             st.push(node);
  25.             node = node->left;
  26.         }
  27.         node = st.top();
  28.         if (node->right == nullptr || node->right == last) {
  29.             cout << node->val << " ";
  30.             st.pop();
  31.             last = node;
  32.             node = nullptr;
  33.         } else {
  34.             node = node->right;
  35.         }
  36.     }
  37. }

2. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

     3
    / \
   9  20
 /  \
15   7

返回它的最大深度 3 。

出处：

https://bbs.csdn.net/topics/604364348

代码：

  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <queue>
  5. #define null INT_MIN
  6. using namespace std;
  7.  
  8. struct TreeNode
  9. {
  10.     int val;
  11.     TreeNode *left, *right;
  12.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  13. };
  14.  
  15. class Solution
  16. {
  17. public:
  18. int maxDepth(TreeNode* root) {
  19.     if (!root) return 0;
  20.     stack<pair<TreeNode*, int>> s;
  21.     int maxDep = 0;
  22.     s.push(make_pair(root, 1));
  23.     while (!s.empty()) {
  24.         TreeNode* cur = s.top().first;
  25.         int curDep = s.top().second;
  26.         s.pop();
  27.         if (cur) {
  28.             maxDep = max(maxDep, curDep); 
  29.             s.push(make_pair(cur->left, curDep + 1));
  30.             s.push(make_pair(cur->right, curDep + 1));
  31.         }
  32.     }
  33.     return maxDep;
  34. }
  35. };
  36.  
  37. TreeNode* buildTree(vector<int>& nums)
  38. {
  39.     if (nums.empty()) return nullptr;
  40. TreeNode *root = new TreeNode(nums.front());
  41.     queue<TreeNode*> q;
  42.     q.push(root);
  43.     int i = 1;
  44.     while(!q.empty() && i < nums.size())
  45.     {
  46.         TreeNode *cur = q.front();
  47.         q.pop();
  48.         if(i < nums.size() && nums[i] != null)
  49.         {
  50.             cur->left = new TreeNode(nums[i]);
  51.             q.push(cur->left);
  52.         }
  53.         i++;
  54.         if(i < nums.size() && nums[i] != null)
  55.         {
  56.             cur->right = new TreeNode(nums[i]);
  57.             q.push(cur->right);
  58.         }
  59.         i++;
  60.     }
  61.     return root;
  62. }
  63.  
  64. int main()
  65. {
  66.     Solution s;
  67. vector<int> nums = {3,9,20,null,null,15,7};
  68.     TreeNode *root = buildTree(nums);
  69. cout << s.maxDepth(root) << endl;
  70.  
  71. nums = {1,null,2,null,3,null,4};
  72.     root = buildTree(nums);
  73. cout << s.maxDepth(root) << endl;
  74.  
  75.     return 0;
  76. }

输出：

3
4

递归法：

  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <queue>
  5. #define null INT_MIN
  6. using namespace std;
  7.  
  8. struct TreeNode
  9. {
  10.     int val;
  11.     TreeNode *left, *right;
  12.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  13. };
  14.  
  15. class Solution
  16. {
  17. public:
  18. int maxDepth(TreeNode* root) {
  19.     if (!root) return 0; 
  20.     int ldepth = maxDepth(root->left);
  21.     int rdepth = maxDepth(root->right);
  22.     return max(ldepth, rdepth) + 1;
  23. }
  24. };
  25.  
  26. TreeNode* buildTree(vector<int>& nums)
  27. {
  28.     if (nums.empty()) return nullptr;
  29. TreeNode *root = new TreeNode(nums.front());
  30.     queue<TreeNode*> q;
  31.     q.push(root);
  32.     int i = 1;
  33.     while(!q.empty() && i < nums.size())
  34.     {
  35.         TreeNode *cur = q.front();
  36.         q.pop();
  37.         if(i < nums.size() && nums[i] != null)
  38.         {
  39.             cur->left = new TreeNode(nums[i]);
  40.             q.push(cur->left);
  41.         }
  42.         i++;
  43.         if(i < nums.size() && nums[i] != null)
  44.         {
  45.             cur->right = new TreeNode(nums[i]);
  46.             q.push(cur->right);
  47.         }
  48.         i++;
  49.     }
  50.     return root;
  51. }
  52.  
  53. int main()
  54. {
  55.     Solution s;
  56. vector<int> nums = {3,9,20,null,null,15,7};
  57.     TreeNode *root = buildTree(nums);
  58. cout << s.maxDepth(root) << endl;
  59.  
  60. nums = {1,null,2,null,3,null,4};
  61.     root = buildTree(nums);
  62. cout << s.maxDepth(root) << endl;
  63.  
  64.     return 0;
  65. }

3. 有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 按 严格递增 顺序排列

出处：

https://edu.csdn.net/practice/23819519

代码：

  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. #include <queue>
  5. #define null INT_MIN
  6. using namespace std;
  7.  
  8. struct TreeNode
  9. {
  10.     int val;
  11.     TreeNode *left, *right;
  12.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  13. };
  14.  
  15. class Solution
  16. {
  17. public:
  18.     TreeNode *sortedArrayToBST(vector<int> &nums)
  19.     {
  20.         return dfs(nums, 0, nums.size() - 1);
  21.     }
  22.     TreeNode *dfs(vector<int> &nums, int left, int right)
  23.     {
  24.         if (left > right)
  25.             return NULL;
  26.         int mid = (left + right) / 2;
  27.         TreeNode *t = new TreeNode(nums[mid]);
  28.         t->left = dfs(nums, left, mid - 1);
  29.         t->right = dfs(nums, mid + 1, right);
  30.         return t;
  31.     }
  32. };
  33.  
  34. vector<int> levelOrder(TreeNode* root) {
  35.     vector<int> res;
  36.     if (!root) return res;
  37.     queue<TreeNode*> q;
  38.     q.push(root);
  39.     while (!q.empty()) {
  40.         TreeNode* cur = q.front();
  41.         q.pop();
  42.         if (cur) {
  43.             res.push_back(cur->val); 
  44.             q.push(cur->left);
  45.             q.push(cur->right);
  46.         } else {
  47.             res.push_back(null);
  48.         }
  49.     }
  50.     for(int i = res.size(); i > 0 && res[i-1] == null; i--)
  51.     res.pop_back();
  52.     return res;
  53. }
  54.  
  55. string vectorToString(vector<int> vect) {
  56.     stringstream ss;
  57. ss << "[";
  58.     for (size_t i = 0; i < vect.size(); i++)
  59. {
  60.         ss << (vect[i] == null ? "null" : to_string(vect[i]));
  61.         ss << (i < vect.size() - 1 ? "," : "]");
  62.     }
  63.     return ss.str();
  64. }
  65.  
  66. int main()
  67. {
  68.     Solution s;
  69. vector<int> nums = {-10,-3,0,5,9};
  70.     TreeNode *bst = s.sortedArrayToBST(nums);
  71. cout << vectorToString(levelOrder(bst)) << endl;
  72.  
  73. nums = {1,3};
  74.     bst = s.sortedArrayToBST(nums);
  75. cout << vectorToString(levelOrder(bst)) << endl;
  76.  
  77.     return 0;
  78. }

输出：

[0,-10,5,null,-3,null,9]
[1,null,3]

代码2：

  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. #include <queue>
  5. #define null INT_MIN
  6. using namespace std;
  7.  
  8. struct TreeNode
  9. {
  10.     int val;
  11.     TreeNode *left, *right;
  12.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  13. };
  14.  
  15. class Solution
  16. {
  17. public:
  18. TreeNode* sortedArrayToBST(vector<int>& nums) {
  19.     if (nums.empty()) return nullptr;
  20.     int mid = nums.size() / 2;
  21.     TreeNode* root = new TreeNode(nums[mid]);
  22.     vector<int> left(nums.begin(), nums.begin() + mid);
  23.     vector<int> right(nums.begin() + mid + 1, nums.end());
  24.     root->left = sortedArrayToBST(left);
  25.     root->right = sortedArrayToBST(right);
  26.     return root;
  27. }
  28. };
  29.  
  30. vector<int> levelOrder(TreeNode* root) {
  31.     vector<int> res;
  32.     if (!root) return res;
  33.     queue<TreeNode*> q;
  34.     q.push(root);
  35.     while (!q.empty()) {
  36.         TreeNode* cur = q.front();
  37.         q.pop();
  38.         if (cur) {
  39.             res.push_back(cur->val); 
  40.             q.push(cur->left);
  41.             q.push(cur->right);
  42.         } else {
  43.             res.push_back(null);
  44.         }
  45.     }
  46.     for(int i = res.size(); i > 0 && res[i-1] == null; i--)
  47.     res.pop_back();
  48.     return res;
  49. }
  50.  
  51. string vectorToString(vector<int> vect) {
  52.     stringstream ss;
  53. ss << "[";
  54.     for (size_t i = 0; i < vect.size(); i++)
  55. {
  56.         ss << (vect[i] == null ? "null" : to_string(vect[i]));
  57.         ss << (i < vect.size() - 1 ? "," : "]");
  58.     }
  59.     return ss.str();
  60. }
  61.  
  62. int main()
  63. {
  64.     Solution s;
  65. vector<int> nums = {-10,-3,0,5,9};
  66.     TreeNode *bst = s.sortedArrayToBST(nums);
  67. cout << vectorToString(levelOrder(bst)) << endl;
  68.  
  69. nums = {1,3};
  70.     bst = s.sortedArrayToBST(nums);
  71. cout << vectorToString(levelOrder(bst)) << endl;
  72.  
  73.     return 0;
  74. }

输出：

[0,-3,9,-10,null,5]
[3,1]

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览43883 人正在系统学习中
PythonTogether
微信公众号
一起来学派森吧
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪