笔试面试题——二叉树进阶（二）

发布时间：2024年01月22日

在这里插入图片描述


📘北尘_：个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》
??走在路上，不忘来时的初心

文章目录

一、二叉搜索树与双向链表

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解+递归展开图

在这里插入图片描述

在这里插入图片描述

3、代码实现

class Solution {
public:
	void _Convert(TreeNode* cur,TreeNode*& prev)
	{
		if(cur==nullptr)
			return;
		_Convert(cur->left,prev);
		cur->left=prev;
		if(prev)
		{
			prev->right=cur;
		}
		prev=cur;

		_Convert(cur->right,prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
		TreeNode* cur=pRootOfTree,*prev=nullptr;
		 _Convert(cur,prev);

		TreeNode* root=pRootOfTree;
		while(root && root->left)
		{
			root=root->left;
		}
		return root;   
    }
};

二、从前序遍历和中序遍历中构建二叉树

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解+递归展开图

在这里插入图片描述

在这里插入图片描述

3、代码实现

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& i,int begin,int end)
    {
        if(begin>end)
           return nullptr;
        int rooti=begin;
        while(rooti<=end)
        {
            if(preorder[i]==inorder[rooti])
               break;
            rooti++;
        }
        TreeNode* root=new TreeNode(preorder[i++]);
        root->left=_buildTree(preorder,inorder,i,begin,rooti-1);
        root->right=_buildTree(preorder,inorder,i,rooti+1,end);
        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i=0;
        TreeNode* root=_buildTree(preorder,inorder,i,0,inorder.size()-1);
        return root;
    }
};

三、从中序遍历和后序遍历中构建二叉树

1、题目讲解

在这里插入图片描述
在这里插入图片描述

2、思路讲解

在这里插入图片描述

3、代码实现

class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,
    int& i,int begin,int end)
    {
        if(begin>end)
            return nullptr;

        int rooti=begin;
        while(begin<=end)
        {
            if(postorder[i]==inorder[rooti])
                break;
            rooti++;
        }
        TreeNode* root=new TreeNode(postorder[i--]);
        root->right=_buildTree(inorder,postorder,i,rooti+1,end);
        root->left=_buildTree(inorder,postorder,i,begin,rooti-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i=postorder.size()-1;
        TreeNode* root=_buildTree(inorder,postorder,i,0,inorder.size()-1);
        return root;

    }
};
文章来源:https://blog.csdn.net/2301_78995005/article/details/135757498
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章