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

根据二叉树创建字符串

题目：

样例：


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

思路

结合题目和样例，我们可以知道，特殊的是右子树存在但是左子树不存在的情况，这种情况，可以归类为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赋值给parent
		root->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)
    {
        //当左边大于右边的时候返回nullptr
        if(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);
    }
};

总结

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