二叉树的OJ题——C++

编程入门行业动态更新时间:2024-10-28 00:18:06

二叉树的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;}