「二叉树进阶题解：构建、遍历与结构转化全解析」

根据二叉树创建字符串

题目：

样例：


可以看见，唯一特殊的就是左子树，当右子树存在的时候左子树不存在的时候，我们需要用()代表空，但是没有左子树，又没有右子树的时候，我们不需要做任何处理。

思路

结合题目和样例，我们可以知道，特殊的是右子树存在但是左子树不存在的情况，这种情况，可以归类为root->left||root->right。这种情况，我们就要处理左子树。首先我们应该处理一下需要返回的字符串，

1. 有左子树的情况，当有左子树的时候，我们直接递归左子树，并将结果加上()
2. 没有左子树，但是有有右子树，也需要递归一次左子树，因为需要加上空的()
3. 有右子树，直接递归右子树，最后在结果上加上()。

代码

class Solution {
public:string tree2str(TreeNode* root) {if(root==nullptr) return  "";string result=to_string(root->val);if(root->left||root->right){result+="("+tree2str(root->left)+")";}if(root->right){result+="("+tree2str(root->right)+")";}return result;}
};

二叉树的层序遍历

题目：

样例：

思路

这道题可以直接借助队列，借助队列的时候我们还需要一个levelsize来记录每层的个数即可

代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root==nullptr)return vector<vector<int>>();//创建队列queue<TreeNode*> q;q.push(root);vector<vector<int>> result;int levelsize=1;while(!q.empty()){vector<int> level;for(int i=0;i<levelsize;i++){auto front=q.front();q.pop();if(front->left)q.push(front->left);if(front->right)q.push(front->right);level.push_back(front->val);}result.push_back(level);levelsize=q.size();}return result;}
};

二叉树的最近公共祖先

题目：

样例：

思路

需要找公共祖先，首先我们肯定要找到这两个节点的位置，然后这两个节点向上返回，我们用left表示是向左子树搜索这个节点，用right表示向右子树搜索这两个节点，如果能找到就返回对应的节点，p或者q，如果没找到就返回nullptr，如果left和right都不为空说明p和q分布在左子树和右子树，并且root就是两个的最近的祖先，如果其中一个是nullptr说明，p和q分布在一边，直接返回不为空的那个就是最近公共祖先。

代码

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//找对应的节点if(root==nullptr||root==p||root==q)return root;//记录左子树的结果TreeNode* left=lowestCommonAncestor(root->left,p,q);//记录右子树的结果TreeNode* right=lowestCommonAncestor(root->right,p,q);//如果左右子树都不为空则说明和q分布在左子树和右子树if(left&&right)return root;//如果其中一个是空，则说明p是祖先或者q是祖先return (left==nullptr)?right:left;}
};

二叉搜索树与双向链表

题目：

样例：

思路

首先我们来看看子问题：
这肯定是一个中序遍历吧，因为只有中序遍历才能是顺序的，这很明显，接下来就是我们需要处理的中序中间的部分，就是节点之间关系的转变。

从这里可以知道左指针是指向前驱的指针，右指针是指向后继的指针。

这里我们分别对左子树和右子树进行中序遍历，第一个遍历到4，因为4是第一个，所以前驱应该是nullptr，因为每次我们都需要前驱，所以这里我们用parent表示前驱，parent就应该被初始化为nullptr，当中序遍历到达4的时候4是不需要处理的因为4的左子树和右子树都是nullptr，唯一需要处理的就是4的前驱应该是nullptr，处理完之后，我们需要返回前驱，因为6需要指向前驱，前驱不为空的情况下还需要将前驱的右指针指向后继，4的后继是6，所以我们只需要进行两个步骤，第一个步骤是处理前驱，前驱是已知节点指向前驱节点，所以我们不用担心是否为空，因为我们的前驱parent初始化是nullptr，所以在parent指向后继的时候，需要判断一下parent是否是空。
最后再改变前驱即可左子树的前驱就是最后一个访问的节点，左中右，所以上图应该是8。

代码

class Solution {
public:TreeNode* parent=nullptr;void InOrder(TreeNode* root){//root是nullptr返回if(!root)return;//中序遍历InOrder(root->left);//先将root的前驱指针指向parent，root赋值给parentroot->left = parent;if(parent) parent->right=root;parent = root;InOrder(root->right);}//左指针指向前面，右指针指向后面TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree==nullptr)return nullptr;TreeNode* first=pRootOfTree;while(first->left) first=first->left;InOrder(pRootOfTree);return first;}
};

从前序与中序遍历序列构造二叉树

题目：

样例：

思路

首先已知两个序列：

前序和中序，根据前序的特性我们可以知道，第一个元素肯定是根节点，所以这里我们可以根据前序遍历找到根节点，然后在中序遍历中找到根节点的位置。

找到在中序中的位置之后我们可以通过中序的特性，左边是左子树，右边是右子树，来对左区间和右区间递归，根节点的left指向左区间，根节点的right指向右区间，然后循环这个过程。

代码

class Solution {
public://构建二叉树TreeNode* Build(vector<int>& preorder,int preL,int preR,vector<int> inorder,int inL,int inR){//当左边大于右边的时候返回nullptrif(preL>preR)return nullptr;//找出根节点的值int rootval=preorder[preL];TreeNode *root=new TreeNode(rootval);//找到在中序遍历中的位置int index=inL;while(inorder[index]!=rootval) index++;//计算左子树在前序中的位置int leftSize=index-inL;root->left=Build(preorder,preL+1,preL+leftSize,inorder,inL,index-1);root->right=Build(preorder,preL+leftSize+1,preR,inorder,index+1,inR);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return Build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);}
};

总结

通过多道二叉树题目的练习，我们全面了解了二叉树的各种操作和特性。每道题目都涉及不同的场景和技巧，如节点删除、树的遍历、以及特殊结构转换等，不仅加深了对二叉树结构的理解，也提升了编写递归和迭代算法的能力。这些经验为进一步深入数据结构和算法的学习打下了扎实的基础。希望这篇总结能够帮助你在二叉树题目中更得心应手，为更复杂的数据结构问题做好准备。