目录

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

代码：递归算法

#include #include #include using namespace std;struct TreeNode{int val;TreeNode *left, *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution{private:void rec(TreeNode *root, vector &ret){if (root != nullptr){ret.push_back(root->val);rec(root->right, ret);rec(root->left, ret);}}public:vector postorderTraversal(TreeNode *root){vector ret;rec(root, ret);return ret;}};string Vector2String(vector vect) {stringstream ss;ss << "[";for (size_t i = 0; i < vect.size(); i++){ss << to_string(vect[i]);ss << (i right = new TreeNode(2);root->right->left = new TreeNode(3);Solution s;cout << Vector2String(s.postorderTraversal(root)) << endl;return 0;}

输出：

[2,1,3]

进阶： 迭代算法

#include #include #include #include #include #define null INT_MINusing namespace std;struct TreeNode{int val;TreeNode *left, *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};TreeNode* buildTree(vector& nums){if (nums.empty()) return nullptr;TreeNode *root = new TreeNode(nums.front());queue q;q.push(root);int i = 1;while(!q.empty() && i < nums.size()){TreeNode *cur = q.front();q.pop();if(i left = new TreeNode(nums[i]);q.push(cur->left);}i++;if(i right = new TreeNode(nums[i]);q.push(cur->right);}i++;}return root;}void preorderPrint(TreeNode* root) {stack st;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();if (node != nullptr) {cout <val <right);st.push(node->left);}}cout << endl;}void preorderPrint2(TreeNode* root) {stack st;TreeNode* node = root;while (node != nullptr || !st.empty()) {while (node != nullptr) {cout <val <left;}node = st.top();st.pop();node = node->right;}cout << endl;}vector preorderTraversal(TreeNode* root) {vector res;stack st;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();if (node != nullptr) {res.push_back(node->val);st.push(node->right);st.push(node->left);}}return res;}vector preorderTraversal2(TreeNode* root) {vector res;stack st;TreeNode* node = root;while (node != nullptr || !st.empty()) {while (node != nullptr) {res.push_back(node->val);st.push(node);node = node->left;}node = st.top();st.pop();node = node->right;}return res;}string vectorToString(vector vect) {stringstream ss;ss << "[";for (size_t i = 0; i < vect.size(); i++){ss << (vect[i] == null ? "null" : to_string(vect[i]));ss << (i < vect.size() - 1 ? "," : "]");}return ss.str();}int main(){vector nums = {1,null,2,3};TreeNode *root = buildTree(nums);preorderPrint(root);preorderPrint2(root);cout << vectorToString(preorderTraversal(root)) << endl;cout << vectorToString(preorderTraversal2(root)) << endl;nums = {3,9,20,null,null,15,7};root = buildTree(nums);preorderPrint(root);preorderPrint2(root);cout << vectorToString(preorderTraversal(root)) << endl; cout << vectorToString(preorderTraversal2(root)) << endl;nums = {1,2,3,4,5,6,7};root = buildTree(nums);preorderPrint(root);preorderPrint2(root);cout << vectorToString(preorderTraversal(root)) << endl;cout << vectorToString(preorderTraversal2(root)) << endl;return 0;}

输出：

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]

中序后序对比：

//中序遍历void inorder(TreeNode* root) {stack st;TreeNode* node = root;while (!st.empty() || node != nullptr) {while (node != nullptr) {st.push(node);node = node->left;}node = st.top();st.pop();cout <val <right;}}//后序遍历void postorder(TreeNode* root) {stack st;TreeNode* node = root;TreeNode* last = nullptr;while (!st.empty() || node != nullptr) {while (node != nullptr) {st.push(node);node = node->left;}node = st.top();if (node->right == nullptr || node->right == last) {cout <val <right;}}}

2. 二叉树的最大深度

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

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

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

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

 3/ \ 920 /\15 7

返回它的最大深度3 。

出处：

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

代码：

#include #include #include #include #define null INT_MINusing namespace std;struct TreeNode{int val;TreeNode *left, *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution{public:int maxDepth(TreeNode* root) {if (!root) return 0;stack<pair> s;int maxDep = 0;s.push(make_pair(root, 1));while (!s.empty()) {TreeNode* cur = s.top().first;int curDep = s.top().second;s.pop();if (cur) {maxDep = max(maxDep, curDep); s.push(make_pair(cur->left, curDep + 1));s.push(make_pair(cur->right, curDep + 1));}}return maxDep;}};TreeNode* buildTree(vector& nums){if (nums.empty()) return nullptr;TreeNode *root = new TreeNode(nums.front());queue q;q.push(root);int i = 1;while(!q.empty() && i < nums.size()){TreeNode *cur = q.front();q.pop();if(i left = new TreeNode(nums[i]);q.push(cur->left);}i++;if(i right = new TreeNode(nums[i]);q.push(cur->right);}i++;}return root;}int main(){Solution s;vector nums = {3,9,20,null,null,15,7};TreeNode *root = buildTree(nums);cout << s.maxDepth(root) << endl;nums = {1,null,2,null,3,null,4};root = buildTree(nums);cout << s.maxDepth(root) << endl;return 0;}

输出：

3
4

递归法：

#include #include #include #include #define null INT_MINusing namespace std;struct TreeNode{int val;TreeNode *left, *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution{public:int maxDepth(TreeNode* root) {if (!root) return 0; int ldepth = maxDepth(root->left);int rdepth = maxDepth(root->right);return max(ldepth, rdepth) + 1;}};TreeNode* buildTree(vector& nums){if (nums.empty()) return nullptr;TreeNode *root = new TreeNode(nums.front());queue q;q.push(root);int i = 1;while(!q.empty() && i < nums.size()){TreeNode *cur = q.front();q.pop();if(i left = new TreeNode(nums[i]);q.push(cur->left);}i++;if(i right = new TreeNode(nums[i]);q.push(cur->right);}i++;}return root;}int main(){Solution s;vector nums = {3,9,20,null,null,15,7};TreeNode *root = buildTree(nums);cout << s.maxDepth(root) << endl;nums = {1,null,2,null,3,null,4};root = buildTree(nums);cout << s.maxDepth(root) << endl;return 0;}

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

代码：

#include #include #include #include #define null INT_MINusing namespace std;struct TreeNode{int val;TreeNode *left, *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution{public:TreeNode *sortedArrayToBST(vector &nums){return dfs(nums, 0, nums.size() - 1);}TreeNode *dfs(vector &nums, int left, int right){if (left > right)return NULL;int mid = (left + right) / 2;TreeNode *t = new TreeNode(nums[mid]);t->left = dfs(nums, left, mid - 1);t->right = dfs(nums, mid + 1, right);return t;}};vector levelOrder(TreeNode* root) {vector res;if (!root) return res;queue q;q.push(root);while (!q.empty()) {TreeNode* cur = q.front();q.pop();if (cur) {res.push_back(cur->val); q.push(cur->left);q.push(cur->right);} else {res.push_back(null);}}for(int i = res.size(); i > 0 && res[i-1] == null; i--)res.pop_back();return res;}string vectorToString(vector vect) {stringstream ss;ss << "[";for (size_t i = 0; i < vect.size(); i++){ss < nums = {-10,-3,0,5,9};TreeNode *bst = s.sortedArrayToBST(nums);cout << vectorToString(levelOrder(bst)) << endl;nums = {1,3};bst = s.sortedArrayToBST(nums);cout << vectorToString(levelOrder(bst)) << endl;return 0;}

输出：

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

代码2：

#include #include #include #include #define null INT_MINusing namespace std;struct TreeNode{int val;TreeNode *left, *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class Solution{public:TreeNode* sortedArrayToBST(vector& nums) {if (nums.empty()) return nullptr;int mid = nums.size() / 2;TreeNode* root = new TreeNode(nums[mid]);vector left(nums.begin(), nums.begin() + mid);vector right(nums.begin() + mid + 1, nums.end());root->left = sortedArrayToBST(left);root->right = sortedArrayToBST(right);return root;}};vector levelOrder(TreeNode* root) {vector res;if (!root) return res;queue q;q.push(root);while (!q.empty()) {TreeNode* cur = q.front();q.pop();if (cur) {res.push_back(cur->val); q.push(cur->left);q.push(cur->right);} else {res.push_back(null);}}for(int i = res.size(); i > 0 && res[i-1] == null; i--)res.pop_back();return res;}string vectorToString(vector vect) {stringstream ss;ss << "[";for (size_t i = 0; i < vect.size(); i++){ss << (vect[i] == null ? "null" : to_string(vect[i]));ss << (i < vect.size() - 1 ? "," : "]");}return ss.str();}int main(){Solution s;vector nums = {-10,-3,0,5,9};TreeNode *bst = s.sortedArrayToBST(nums);cout << vectorToString(levelOrder(bst)) << endl;nums = {1,3};bst = s.sortedArrayToBST(nums);cout << vectorToString(levelOrder(bst)) << endl;return 0;}

输出：

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

每日一练刷题专栏

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

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

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

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

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

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏