【每日刷题】Day128
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 606. 根据二叉树创建字符串 - 力扣（LeetCode）
2. LCR 194. 二叉树的最近公共祖先 - 力扣（LeetCode）
3. LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣（LeetCode）
1. 606. 根据二叉树创建字符串 - 力扣（LeetCode）
//思路：前序遍历+判断。
//根据题目给的例子我们就能明白本题的要求：将子树用括号括起来，空树用一对空括号"()"表示。如果左子树不为空，右子树为空，则右子树的"()"应当省略；如果左子树为空，右子树不为空，则左子树的"()"不能省略；如果左右子树均为空，也就是叶子节点，则左右子树的"()"都要省略。
class Solution {
public:
bool IsLeafNode(TreeNode* root)//判断是否为叶子节点
{
return !root->left&&!root->right;
}
string tree2str(TreeNode* root)
{
string ans;
if(!root) return ans;//遍历到空树，返回空字符串
if(IsLeafNode(root))//如果是叶子节点，则左右子树的"()"均省略
{
ans+=to_string(root->val);
return ans;
}
ans+=to_string(root->val);
ans+='(';
ans+=tree2str(root->left);
ans+=')';
if(root->right) ans+='(';//判断右树是否为空
ans+=tree2str(root->right);
if(root->right) ans+=')';
return ans;
}
};
2. LCR 194. 二叉树的最近公共祖先 - 力扣（LeetCode）
//思路：找规律+深搜。
//本题有一个非常重要的规律：
class Solution {
public:
bool IsInTree(TreeNode* f,TreeNode* x)//去当前 f 节点的子树中查找 x 节点
{
if(!f) return false;
if(f==x) return true;
return IsInTree(f->left,x)||IsInTree(f->right,x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!root) return nullptr;
bool left1 = IsInTree(root->left,p);//去当前节点的左树查找 p 节点
bool left2 = IsInTree(root->left,q);//去当前节点的左树查找 q 节点
bool right1 = IsInTree(root->right,p);//去当前节点的右树查找 p 节点
bool right2 = IsInTree(root->right,q);//去当前节点的左树中查找 q 节点
if(root==p&&(left2||right2)) return root;//处理公共祖先为 p 的情况
if(root==q&&(left1||right1)) return root;//处理公共祖先为 q 的情况
if((left1&&right2)||(left2&&right1)) return root;//左边找到了 p 节点并且右边找到了 q 节点 或者 左边找到了 q 节点并且右边找到了 p 节点。则当前节点就是公共祖先
TreeNode* ret1 = lowestCommonAncestor(root->left,p,q);
if(ret1) return ret1;//如果已经找到了，则不需要去右边找，直接返回
TreeNode* ret2 = lowestCommonAncestor(root->right,p,q);
return ret2;
}
};
3. LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣（LeetCode）
//思路1：中序遍历+存储。
//中序遍历一次二叉搜索树，将中序遍历的结果以节点指针的形式存入数组中。
//随后遍历数组对每一个节点的left和right进行修改操作
class Solution {
public:
bool IsLeafNode(Node* root)//判断是否为叶子节点
{
return !root->left&&!root->right;
}
void _treeToDoublyList(Node* root,vector<Node*>& arr)
{
if(!root) return;
_treeToDoublyList(root->left,arr);
arr.push_back(root);//中序遍历，将节点存入数组中
_treeToDoublyList(root->right,arr);
}
Node* treeToDoublyList(Node* root)
{
//处理两个边界情况
if(!root) return nullptr;
if(IsLeafNode(root))
{
root->left = root;
root->right = root;
return root;
}
vector<Node*> arr;
_treeToDoublyList(root,arr);
int size = arr.size();
//处理第一个和最后一个节点
arr[0]->left = arr[size-1];
arr[0]->right = arr[1];
arr[size-1]->right = arr[0];
arr[size-1]->left = arr[size-2];
for(int i = 1;i<size-1;i++)
{
arr[i]->left = arr[i-1];
arr[i]->right = arr[i+1];
}
return arr[0];
}
};
//思路2：双指针+中序遍历。
//这里的思路非常巧妙：我们使用两个指针 cur 和 prev。cur初始为root；prev初始为nullptr。进行如下操作：
class Solution {
public:
void _treeToDoublyList(Node* cur,Node*& prev)//这里 prev 需要传引用，因为要改变实参 prev 的位置
{
if(!cur) return;
_treeToDoublyList(cur->left,prev);
cur->left = prev;//双指针操作
if(prev) prev->right = cur;
prev = cur;
_treeToDoublyList(cur->right,prev);
}
Node* treeToDoublyList(Node* root)
{
if(!root) return nullptr;
Node* prev = nullptr;
_treeToDoublyList(root,prev);
Node* head = root;//找链表头
while(head->left) head = head->left;
head->left = prev;
prev->right = head;
return head;
}
};
