二叉树的OJ题——C++"/>
二叉树的OJ题——C++
一、根据二叉树创建字符串
题目链接:
606. 根据二叉树创建字符串 - 力扣(LeetCode)
题目描述:
前序遍历二叉树,并且将结果存入到一个string中,并且要使用括号去分割和表示每个节点和子树之间的关系,并且要求省略掉可以省略的括号
解题思路:
根据题意,就是一个二叉树前序递归的问题,对是否省略的问题上分类讨论一下即可
参考代码:
class Solution
{
public:string tree2str(TreeNode* root) {if(root == nullptr){return "";}string ret = to_string(root->val);if(root->left || root->right){ret+="(";ret+= tree2str(root->left);ret+=")";}if(root->right){ret+="(";ret+=tree2str(root->right);ret+=")";}return ret;}
};
二、二叉树的层序遍历
题目链接:
102. 二叉树的层序遍历 - 力扣(LeetCode)
题目描述:
二叉树的层序遍历,就是对二叉树一层一层的进行遍历,题目要求将遍历的结果存在一个二维数组里返回。
解题思路:
利用一个队列,每遍历一个节点,就将该节点的左子树和右子树的根放入队列,每次取队头元素遍历,有种排队进出的感觉,由于需要一层一层的出,因此从第一层开始,就用一个size去记录每一层的个数,通过size去控制每一层出几次,遇到空则不入队列
参考代码:
vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;queue<TreeNode*> q;int num;if(root !=nullptr){q.push(root);}while(!q.empty()){num = q.size();vector<int> tmp;while(num--){TreeNode* node = q.front();if(node->left != nullptr){q.push(node->left);}if(node->right != nullptr){q.push(node->right);} tmp.push_back(node->val); q.pop();}ret.push_back(tmp);}return ret;}
拓展:
反向层序遍历,要求反向层序遍历,没有特殊要求,则直接将结果逆置即可
107. 二叉树的层序遍历 II - 力扣(LeetCode)
三、二叉树的最近公共祖先
题目链接:
236. 二叉树的最近公共祖先 - 力扣(LeetCode)
题目描述:
找两个节点p和q的最近的公共祖先,并且节点本身也能成为祖先,不存在找不到的测试用例
解题思路:
思路一:
通过观察可以发现,当p和q分别在一个节点的左子树和右子树时,这个节点就一定是p和q的最近公共祖先
思路二:
关键在Path如何实现
参考代码:
思路一:
bool FindNode(TreeNode* root,TreeNode* goal){if(root == nullptr){return false;}if(root == goal){return true;}return FindNode(root->left,goal) || FindNode(root->right,goal);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr){return nullptr;}if(root == p){return root;}if(root == q){return root;}bool q_left = FindNode(root->left,q);bool q_right = !q_left;bool p_left = FindNode(root->left,p);bool p_right = !p_left;if((q_left && p_right) || (q_right && p_left)){return root;}else if(q_left && p_left){return lowestCommonAncestor(root->left,p,q);}else{return lowestCommonAncestor(root->right,p,q);} }
思路二:
bool Path(TreeNode* root,TreeNode* goal,stack<TreeNode*>& st){ if(root == nullptr){return false;}st.push(root);if(root == goal){return true;}if(Path(root->left,goal,st)){return true;}if(Path(root->right,goal,st)){return true;}else{st.pop();return false;}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> st_p;stack<TreeNode*> st_q;Path(root,p,st_p);Path(root,q,st_q);while(st_p.size() > st_q.size()){st_p.pop();}while(st_p.size() < st_q.size()){st_q.pop();}while(st_p.top() != st_q.top()){st_p.pop();st_q.pop();}return st_p.top();}
四、二叉搜索树与双向链表
题目链接:
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder)
题目描述:
将一颗二叉搜索树转换为一个有序的双向不循环链表,然后返回任意一边的节点,并且要求在原树上进行改造,不允许额外的开空间。
解题思路:
首先,需要有序的遍历二叉搜索树,我们需要使用中序遍历,在中序遍历中,我们需要一边走,一边改变指针的方向,使得前后相互链接,因此我们可以两个指针一起走,同时遍历,记录每一步的前一个节点,并且将他们两个互相链接起来,最后遍历完整棵树,也就改造好了
参考代码:
void InOrder(TreeNode* root, TreeNode*& prev) {if (root == nullptr)return;InOrder(root->left, prev);root->left = prev;if (prev)prev->right = root;prev = root;InOrder(root->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev = nullptr;InOrder(pRootOfTree, prev);TreeNode* head = pRootOfTree;while(head && head->left){head = head->left;}return head;}
五、根据前序与中序遍历序列构造二叉树
题目链接:
105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)
题目描述:
题目给了一个二叉树前序遍历后的序列和中序遍历后的序列,需要我们根据这两个序列还原构建一个二叉树
解题思路:
首先要知道,如果根据前序和中序序列去还原一颗二叉树,我们需要通过前序序列去确定根,然后在中序序列中找到根的位置,把根位置的两边分别分割成左子树和右子树,然后继续去前序序列中确定子树的根,直到将前序遍历完,也就能够完整分割中序序列,重新构建回一个二叉树
参考代码:
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend){if(inbegin > inend){return nullptr;}int root_val = preorder[prei++];TreeNode* root = new TreeNode(root_val);//找到在中序序列中根的位置,分割区间int rooti = inbegin;while(inorder[rooti] != root_val){rooti++;}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 prei = 0;return _buildTree(preorder,inorder,prei,0,inorder.size()-1);}
拓展:
通过中序遍历和后序遍历序列重构二叉树,思路上和这个类似
106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)
六、非递归_前序遍历
题目链接:
144. 二叉树的前序遍历 - 力扣(LeetCode)
题目描述:
用非递归的方式走前序遍历
解题思路:
我们需要借助一个栈,将问题划分为两步,一是先左边的节点全部入栈,然后再一个个出栈解决每个节点的右子树,每个右子树又得当成子问题一样处理
参考代码:
vector<int> preorderTraversal(TreeNode* root) {vector<int> ret;stack<TreeNode*> st;TreeNode* cur = root;while(cur || !st.empty()){while(cur){ret.push_back(cur->val);st.push(cur);cur=cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;}return ret;}
拓展:
非递归_中序遍历和非递归_后序遍历,思路上一样,后序遍历需要一定的特殊处理
94. 二叉树的中序遍历 - 力扣(LeetCode)
145. 二叉树的后序遍历 - 力扣(LeetCode)
后序遍历的处理,需要对什么时候取节点的值需要进行判断,根据画图分析,将情况分类为两种,一种是栈顶元素的右子树为空时,则输出,并且将该节点pop掉,当右子树不为空时,则需要进一步对右子树的值进行入栈,并且不能将该节点pop,只有在该节点被输出后才可以pop
对节点什么时候输出分两种情况,一种是左子树走完,右子树为空,另一种是左子树走完,右子树也走完,出栈元素一定是走完左子树的,对于右子树需要进一步判断,而需要判断右子树是否走完则需要额外的一个节prev去记录上一次pop的数据,如果上一次pop的数据是该节点的右子树,则说明该节点走完了右子树,需要输出
更多推荐
二叉树的OJ题——C++
发布评论