二分查找习题
一、二叉搜索树与双向链表（剑指 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();}};