您现在的位置是：首页 > 后端

当前栏目

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

C++二叉树每日专场

2023-09-14 09:01:29 时间

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

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 <iostream>
#include <sstream>
#include <vector>
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<int> &ret)
    {
        if (root != nullptr)
        {
            ret.push_back(root->val);
            rec(root->right, ret);
            rec(root->left, ret);
        }
    }
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> ret;
        rec(root, ret);
        return ret;
    }
};

string Vector2String(vector<int> vect) {
    stringstream ss;
	ss << "[";
    for (size_t i = 0; i < vect.size(); i++)
	{
        ss << to_string(vect[i]);
        ss << (i < vect.size() - 1 ? "," : "]");
    }
    return ss.str();
}

int main()
{
    TreeNode *root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    Solution s;
	cout << Vector2String(s.postorderTraversal(root)) << endl;
    
    return 0;
}

输出：

[2,1,3]

进阶： 迭代算法

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#define null INT_MIN
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(vector<int>& nums)
{
    if (nums.empty()) return nullptr;
	TreeNode *root = new TreeNode(nums.front());
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while(!q.empty() && i < nums.size())
    {
        TreeNode *cur = q.front();
        q.pop();
        if(i < nums.size() && nums[i] != null)
        {
            cur->left = new TreeNode(nums[i]);
            q.push(cur->left);
        }
        i++;
        if(i < nums.size() && nums[i] != null)
        {
            cur->right = new TreeNode(nums[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

void preorderPrint(TreeNode* root) {
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        if (node != nullptr) {
            cout << node->val << " ";
            st.push(node->right);
            st.push(node->left);
        }
    }
    cout << endl;
}

void preorderPrint2(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (node != nullptr || !st.empty()) {
        while (node != nullptr) {
            cout << node->val << " ";
            st.push(node);
            node = node->left;
        }
        node = st.top();
        st.pop();
        node = node->right;
    }
    cout << endl;
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> 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<int> preorderTraversal2(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> 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<int> 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<int> 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<TreeNode*> st;
    TreeNode* node = root;
    while (!st.empty() || node != nullptr) {
        while (node != nullptr) {
            st.push(node);
            node = node->left;
        }
        node = st.top();
        st.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

//后序遍历
void postorder(TreeNode* root) {
    stack<TreeNode*> 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 << node->val << " ";
            st.pop();
            last = node;
            node = nullptr;
        } else {
            node = node->right;
        }
    }
}

2. 二叉树的最大深度

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

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

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

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

返回它的最大深度 3 。

出处：

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

代码：

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#define null INT_MIN
using 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<TreeNode*, int>> 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<int>& nums)
{
    if (nums.empty()) return nullptr;
	TreeNode *root = new TreeNode(nums.front());
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while(!q.empty() && i < nums.size())
    {
        TreeNode *cur = q.front();
        q.pop();
        if(i < nums.size() && nums[i] != null)
        {
            cur->left = new TreeNode(nums[i]);
            q.push(cur->left);
        }
        i++;
        if(i < nums.size() && nums[i] != null)
        {
            cur->right = new TreeNode(nums[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main()
{
    Solution s;
	vector<int> 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 <iostream>
#include <vector>
#include <stack>
#include <queue>
#define null INT_MIN
using 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<int>& nums)
{
    if (nums.empty()) return nullptr;
	TreeNode *root = new TreeNode(nums.front());
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while(!q.empty() && i < nums.size())
    {
        TreeNode *cur = q.front();
        q.pop();
        if(i < nums.size() && nums[i] != null)
        {
            cur->left = new TreeNode(nums[i]);
            q.push(cur->left);
        }
        i++;
        if(i < nums.size() && nums[i] != null)
        {
            cur->right = new TreeNode(nums[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main()
{
    Solution s;
	vector<int> 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 <iostream>
#include <sstream>
#include <vector>
#include <queue>
#define null INT_MIN
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution
{
public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {
        return dfs(nums, 0, nums.size() - 1);
    }
    TreeNode *dfs(vector<int> &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<int> levelOrder(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> 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<int> 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<int> 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 <iostream>
#include <sstream>
#include <vector>
#include <queue>
#define null INT_MIN
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution
{
public:
	TreeNode* sortedArrayToBST(vector<int>& nums) {
	    if (nums.empty()) return nullptr;
	    int mid = nums.size() / 2;
	    TreeNode* root = new TreeNode(nums[mid]);
	    vector<int> left(nums.begin(), nums.begin() + mid);
	    vector<int> right(nums.begin() + mid + 1, nums.end());
	    root->left = sortedArrayToBST(left);
	    root->right = sortedArrayToBST(right);
	    return root;
	}
};

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> 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<int> 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<int> 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每日一练专栏

猜你喜欢

c++ 命名空间 using namespace std 是什么意思?
344. 反转字符串
[Linux] 使用 Mailx 发送测试(邮件基于25、465端口配置，云服务器)
【java8新特性】——Optional详解（三）
ContentProvider插件化解决方案
python中运行scvi整合数据去除批次效应时 gpu可以加速为何GPU可以用于加速人工智能或者机器学习的计算速度（并行计算能力）
Catch That Cow----BFS
macOS aMule安装
使用pymongo将文件存入MongoDB
ASP.NET Core 6框架揭秘实例演示[27]：ASP.NET Core 6 Minimal API的模拟实现
C++类设计的一些心得
[转]C++中关于new和delete的使用
【codeforces 768C】Jon Snow and his Favourite Number
软件测试技术之性能测试进阶—并发测试的方法
[Typescript] 57. Medium - FlattenDepth
reactos操作系统实现(128)
mysql float double 类型
printf打印long long类型数据

相关主题

c++ 函数指针
C++015-C++函数
c++ 多线程编程
c++ 虚方法
【C++】待修改

zl程序教程

当前栏目

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

1. 二叉树的前序遍历

2. 二叉树的最大深度

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

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

相关文章

当前栏目

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

1. 二叉树的前序遍历

2. 二叉树的最大深度

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

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏