C++&数据结构——部分OJ题详解
2023-12-20 17:58:50
根据二叉树创建字符串
题目出处:606. 根据二叉树创建字符串 - 力扣(LeetCode)
class Solution {
public:
string tree2str(TreeNode* root)
{
if (root == nullptr)
return "";
string str = to_string(root->val); //将int类型的val转换成string类型
if (root->left || root->right) //左边或右边不为空,保留左边空括号
{
str += '(';
str += tree2str(root->left);
str += ')';
}
if (root->right) //右边为空时,不需要打印空括号
{
str += '(';
str += tree2str(root->right);
str += ')';
}
return str;
}
};
二叉树的层序遍历(一)
?题目出处:102. 二叉树的层序遍历 - 力扣(LeetCode)
层序遍历即逐层地,从左到右访问所有节点,有两种思路:
①用两个队列,一个队列控制层序遍历的节点,一个控制节点的层数
②通过一个levelSize变量控制队列出的数据数量,当变量出完后用队列的size更新levelSize
class Solution
{
public:
//从头结点开始往下
vector<vector<int>> levelOrder(TreeNode* root)
{
queue<TreeNode*> q;
int levelSize = 0;
if (root)
{
q.push(root);
levelSize = 1; //头结点只有一个
}
vector<vector<int>> vv;
while (!q.empty())
{
vector<int> v;
//通过levelSize控制一层一层出
while (levelSize--)
{
TreeNode* front = q.front(); //先取队头数据
q.pop();
v.push_back(front->val);
//将下一层的节点指针入队列
if (front->left)
q.push(front->left);
if (front->right)
q.push(front->right);
}
//将当前层放到vv里去
vv.push_back(v);
//更新下一层的数据
levelSize = q.size();
}
return vv;
}
};
?二叉树的层序遍历(二)
题目出处:107. 二叉树的层序遍历 II - 力扣(LeetCode)
只需要将上面的层序遍历逆置一下即可?
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root)
{
queue<TreeNode*> q;
int levelSize = 0;
if (root)
{
q.push(root);
levelSize = 1; //头结点只有一个
}
vector<vector<int>> vv;
while (!q.empty())
{
vector<int> v;
//通过levelSize控制一层一层出
while (levelSize--)
{
TreeNode* front = q.front(); //先取队头数据
q.pop();
v.push_back(front->val);
//将下一层的节点指针入队列
if (front->left)
q.push(front->left);
if (front->right)
q.push(front->right);
}
//将当前层放到vv里去
vv.push_back(v);
//更新下一层的数据
levelSize = q.size();
}
reverse(vv.begin(), vv.end());
return vv;
}
};
二叉树的最近公共节点
题目出处:236. 二叉树的最近公共祖先 - 力扣(LeetCode)
方法一
方法一的大体思路是:如果给定的两个节点一个在右树一个在左树,那么这棵树的根节点就是我的公共祖先,所以我们先实现一个函数来判断给定的两个节点在树两边的位置,然后递归去走,如下代码:
class Solution
{
public:
bool IsIntree(TreeNode* root, TreeNode* x)
{
if (root == nullptr)
return false;
return root == x || IsIntree(root->left,x) || IsIntree(root->right,x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (root == nullptr) //空树
return nullptr;
if (p == root || q == root) //p或q有一个是根,root就是最近公共节点
return root;
//判断pq在树的左边还是右边
bool pInLeft = IsIntree(root->left, p);
bool pInRight = !pInLeft;
bool qInLeft = IsIntree(root->left, q);
bool qInRight = !qInLeft;
if ((pInLeft && qInRight) || (qInLeft && pInRight)) //一个在根的左边一个在根的右边,那么根就是最近公共节点
return root;
else if (pInLeft && qInLeft) //都在左树,就递归到左子树去找公共祖先
return lowestCommonAncestor(root->left, p, q);
else //都在右树,就递归到右子树去找公共祖先
return lowestCommonAncestor(root->right, p, q);
}
};
?这是一种思路,但是这种思路有很大缺点,因为必须要求是满二叉树或者完全二叉树的时候时间复杂度才是O(logN),其他的都是O(N^2),所以我们采用方法二会更好
方法二(推荐)
方法二的大体思路和以前数据结构求链表相交节点的那个题目类似,用栈来解决问题,虽然需要申请一点空间,但是可以使时间复杂度搭配O(N),属于典型的空间换时间,如下代码和注释:
class Solution
{
public:
bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& Path)
{
if (root == nullptr)
return false;
Path.push(root);
if (root == x)
return true;
if (GetPath(root->left, x, Path))
return true;
if (GetPath(root->right, x, Path))
return true;
Path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pPath, qPath; //用栈来记录两个节点的路径节点
GetPath(root, p, pPath); //将路径节点依次入栈
GetPath(root, q, qPath);
while (pPath.size() != qPath.size())
{
if (pPath.size() > qPath.size())//长的先走
pPath.pop();
else
qPath.pop();
}
while (pPath.top() != qPath.top()) //依次判断是否为相同祖先节点
{
pPath.pop();
qPath.pop();
}
return pPath.top();
}
};
二叉搜索树与双向链表
题目出处:二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
给的树说二叉搜索树,所以我们以中序遍历来访问树实现排序,?只改变树节点的指向,left为链表的prev,right为链表的next,如下代码:
class Solution
{
public:
void InOrderConvert(TreeNode* cur, TreeNode*& prev) //直接通过中序遍历访问二叉树,
{
if (cur == nullptr)
return;
InOrderConvert(cur->left, prev);
//中序遍历时,使每个节点的left指向前驱节点prev
//让每个节点的right指向prev,将双向链表的节点搞清楚
cur->left = prev; //这里cur出现的顺序顺序就是中序
if (prev) //prev最开始是空,要判断一下
{
prev->right = cur;
}
prev = cur; //往后迭代走
InOrderConvert(cur->right, prev);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* prev = nullptr; //建立前驱节点方便链接
InOrderConvert(pRootOfTree, prev);
TreeNode* head = pRootOfTree;
while (head && head->left) //现在的pRootOfTree是树的根节点位置不是链表头结点位置,一直往前迭代即可
{
head = head->left;
}
return head;
}
};
从前序与中序遍历序列构建二叉树
题目出处:105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)
从题目我么可以看出,前序的整数数组preorder和inorder可以确定根,中序可以分割处左右子树?
class Solution
{
public:
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
{
if (inbegin > inend)
return nullptr;
TreeNode* root = new TreeNode(preorder[prei++]);//每次前序遍历创建根,然后往后走
//根据中序,分割出左右子区间
int rooti = inbegin;
while (rooti <= inend)
{
if (inorder[rooti] == root->val)
{
break;//找到了
}
else
{
rooti++;
}
}
//分割后的区间为[inbegin,rooti-1] ini [rooti,inend]
root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);//创建子树
root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int i = 0;
return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
}
};
文章来源:https://blog.csdn.net/aaqq800520/article/details/135107187
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!