一、二叉搜索树与双向链表（剑指 Offer JZ36 ）
解题思路要点
- 利用中序遍历特性：二叉搜索树的中序遍历结果是有序序列，这是将二叉搜索树转化为有序双向链表的关键。通过中序遍历可以按从小到大的顺序访问节点，满足双向链表有序的要求。
- 指针调整策略：在中序遍历过程中，维护一个前驱节点指针。每当访问到一个新节点时，将新节点的左指针指向之前访问的节点（即前驱节点 ），同时将前驱节点的右指针指向当前节点，逐步构建双向链表的连接关系。
- 头节点确定：在遍历过程中，要记录下
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Inorder(TreeNode* cur,TreeNode* &prev){
if(cur==nullptr){
return;
}
Inorder(cur->left,prev);
cur->left=prev;
if(prev){
prev->right=cur;
}
prev=cur;
Inorder(cur->right,prev);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
TreeNode* prev=nullptr;
Inorder(pRootOfTree,prev);
TreeNode*head=pRootOfTree;
while(head&&head->left){
head=head->left;
}
return head;
}
};
二、根据二叉树创建字符串（LeetCode 606 ）
解题思路要点
- 遍历顺序：明确采用前序遍历方式，先访问根节点，再访问左子树，最后访问右子树。这是因为题目要求按特定顺序将二叉树转化为字符串，前序遍历能满足从根开始构建的需求。
- 空节点处理：对于空节点，用“()”表示。当左子树为空但右子树存在时，左子树对应的“()”不能省略，否则会破坏二叉树与字符串的一一映射关系；若左子树存在，无论右子树是否为空，都按规则添加括号包裹子树转换后的字符串。
- 字符串构建：从根节点开始，依次将节点值和对应子树的字符串按顺序拼接起来。每处理完一个节点及其子树，就得到一部分字符串，最终组合成完整的表示二叉树的字符串。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
string tree2str(TreeNode* root) {
if(root==nullptr)return"";
string str=to_string(root->val);;
if(root->left||root->right){
str+='(';
str+=tree2str(root->left);
str+=')';
}
if(root->right){
str+='(';
str+=tree2str(root->right);
str+=')';
}
return str;
}
};三、二叉树的最近公共祖先（LeetCode 236 ）
解题思路要点
- 递归回溯基础：利用递归从根节点向下探索二叉树。递归的终止条件是遇到空节点或者找到目标节点 p 或 q 。
- 节点判断逻辑：在递归过程中，对每个节点进行判断。如果当前节点就是 p 或 q ，它有可能是最近公共祖先。当从左右子树递归返回后，若左右子树都找到了目标节点（即左右子树返回值都不为空 ），说明当前节点是最近公共祖先；若只有左子树找到目标节点，就返回左子树的结果；若只有右子树找到，就返回右子树的结果；若左右子树都没找到，返回空指针。
- 深度优先搜索：本质上是深度优先搜索的过程，通过不断深入子树，在回溯过程中确定最近公共祖先，保证找到的祖先节点深度尽可能大。
方法一
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool Find(TreeNode* tree,TreeNode* x)
{
if(tree==nullptr)
{
return false;
}
return tree==x||Find(tree->left,x)||Find(tree->right,x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(root==NULL)
{
return NULL;
}
if(root==p||root==q)return root;
bool pinleft,pinright,qinleft,qinright;
pinleft=Find(root->left,p);
pinright=! pinleft;
qinleft=Find(root->left,q);
qinright=! qinleft;
if(pinleft&&qinleft)return lowestCommonAncestor( root->left, p, q);
else if(pinright&&qinright)return lowestCommonAncestor( root->right, p, q);
else return root;
}
};方法二
class Solution {
public:
bool FindPath(TreeNode*root,TreeNode*p,stack<TreeNode*>& Path){
if(root==nullptr)return false;
Path.push(root);
if(root==p)return true;
if(FindPath(root->left,p,Path))return true;
if(FindPath(root->right,p,Path))return true;
Path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
stack<TreeNode*>pPath,qPath;
FindPath(root,p,pPath);
FindPath(root,q,qPath);
while(pPath.size()>qPath.size())pPath.pop();
while(pPath.size()<qPath.size())qPath.pop();
while(pPath.top()!=qPath.top()){
pPath.pop();
qPath.pop();
}
return pPath.top();
}
};