二叉搜索树经典笔试题【力扣、牛客】

1.根据二叉树创建字符串

根据二叉树创建字符串

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* eft, TreeNode* right): val(x), left(left), right(right){}
};//图一分析：
//左不空 (左递归直至遇空返回上一层) 
//然后在当层判断右子树 
//右空 (返回上层 + )
//右不空 (左递归直至遇空返回上一层)
//然后在当层判断右子树 
//右空 (返回上一层 + )//图二分析：
//左不空 (左递归直至遇空返回上一层) 
//然后在当层判断右子树 
//右不空 (左递归直至遇空返回上一层)
//然后在当层判断右子树 
//右空 (返回上层 + )
//右不空 (左递归直至遇空返回上一层)//左不空 右空  --省略
// 左空时第一个if两个条件才判断完
//左空   右空  --省略
//左空  右不空 --不省略
class Solution
{
public:string tree2str(TreeNode* root){if (root == nullptr)return "";string str = to_string(root->val);//遍历完根后遍历左 遍历左的前提是左不空 如果左空看看右空不空//如果右也空没必要遍历 return//如果右不空 正常遍历if (root->left || root->right){str += '(';str += tree2str(root->left);str += ')';}if (root->right) //遍历完左后遍历右 遍历右的前提是右不空 //右不空 正常遍历 右空 【看注释知右空的一律省略 直接return】{str += '(';str += tree2str(root->right);str += ')';}return str;}
};

2. 二叉树的层序遍历

二叉树的层序遍历


点击 二叉树【C】 查看上篇博客中的层序遍历

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* eft, TreeNode* right): val(x), left(left), right(right){}
};class Solution 
{
public:vector<vector<int>> levelorder(TreeNode* root) {queue<TreeNode*> q;int LevelNodeCount = 0;if (root){q.push(root);LevelNodeCount = 1;}vector<vector<int>> vv;while (!q.empty()){vector<int> v;while (LevelNodeCount--){TreeNode* front = q.front();q.pop();v.push_back(front->val);if (front->left)q.push(front->left);if (front->right)q.push(front->right);}vv.push_back(v);LevelNodeCount = q.size();}return vv;}
};

3.二叉树的层序遍历Ⅱ

二叉树的层序遍历Ⅱ

class Solution 
{
public:vector<vector<int>> levelorder(TreeNode* root) {queue<TreeNode*> q;int LevelNodeCount = 0;if (root){q.push(root);LevelNodeCount = 1;}vector<vector<int>> vv;while (!q.empty()){vector<int> v;while (LevelNodeCount--){TreeNode* front = q.front();q.pop();v.push_back(front->val);if (front->left)q.push(front->left);if (front->right)q.push(front->right);}vv.push_back(v);LevelNodeCount = q.size();}reverse(vv.begin(), vv.end());return vv;}
};

4.二叉树的最近公共祖先

二叉树的最近公共祖先

1.法一：定位p、q在左还是右 分类讨论

T(N)=O(N^2)
最坏情况：树为单链即均在左侧或右侧，p、q均在单侧的底部
判断p、q的左右侧时 n-2 n-1
假设p、q均在左侧 接下来递归到左子树 继续判断p、q中是否为根？在左？在右？n-3 n-2 …

class Solution 
{
public:bool IsInTree(TreeNode* root, TreeNode* x){if (root == nullptr)return false;return root == x|| IsInTree(root->left, x)|| IsInTree(root->right,x);}//求p、q的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){if (root == nullptr)return nullptr;//p、q其中一个是根 那么根就为objif (root == p || root == q)return root;//判断p、q在左 ？右bool pInLeft = IsInTree(root->left, p);bool pInRight = !pInLeft;bool qInLeft = IsInTree(root->left, q);bool qInRight = !qInLeft;//一左一右==》root为objif ((pInLeft && qInRight) || (pInRight && qInLeft))return root;//均左==》递归到左子树if (pInLeft && qInLeft)return lowestCommonAncestor(root->left, p, q);//均右==》递归到右子树elsereturn lowestCommonAncestor(root->right, p, q);}
};

2.法二：利用stack求出p、q路径 求相交值

class Solution
{
public:bool GetPath(TreeNode* root, TreeNode* pobj, stack<TreeNode*>& route){if (root == nullptr)return false;route.push(root);if (root == pobj)return true;if (GetPath(root->left, pobj, route))return true;if (GetPath(root->right, pobj, route))return true;route.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pRoute;stack<TreeNode*> qRoute;GetPath(root, p, pRoute);GetPath(root, q, qRoute);//找路径相遇点while (pRoute.size() != qRoute.size()){if (pRoute.size() > qRoute.size())pRoute.pop();elseqRoute.pop();}while (pRoute.top() != qRoute.top()){pRoute.pop();qRoute.pop();}return pRoute.top();}
};

5.二叉搜索树与双向链表

二叉搜索树与双向链表

1.法一：递归：递归过程修正指针指向

class Solution
{
public: //中序遍历void InOrderConvert(TreeNode* cp, TreeNode*& prv){if (cp == nullptr)return;InOrderConvert(cp->left, prv);//一路向左 遇空返回上一层//前左指向前驱cp->left = prv;//left==prv即left指向prv所指向的结点//前驱非空 前结点的right指向后面那个结点if (prv)prv->right = cp;//更新prvprv = cp;//一路向右 遇空返回上一层InOrderConvert(cp->right, prv);}//==》当前层函数结束 返回上一层TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* prev = nullptr;InOrderConvert(pRootOfTree, prev);TreeNode* head = pRootOfTree;//当传一颗空树 head在此就发挥了作用while (head && head->left)head = head->left;return head;}
};

2.数组：将二叉搜索树进行中序遍历可以得到由小到大的顺序排列

/*
struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/class Solution 
{
public:vector<TreeNode*> v;void inorder(TreeNode* root) {if (!root) return;inorder(root->left);v.push_back(root);inorder(root->right);}TreeNode* Convert(TreeNode* pRootOfTree) {if (!pRootOfTree) return pRootOfTree;inorder(pRootOfTree);for (int i = 0; i < v.size() - 1; i++) { v[i]->right = v[i + 1];v[i + 1]->left = v[i];}return v[0];}};

6.前序中序遍历序列构造二叉树

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

class Solution 
{
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& i, int begin, int end){if (begin > end) return nullptr;//遍历inorder 定位到根节点//[begin, x - 1] x [x + 1, end]int x = begin;for (x = begin; x <= end; ++x){if (inorder[x] == preorder[i])break;}TreeNode* root = new TreeNode(preorder[i++]);root->left = _buildTree(preorder, inorder, i, begin, x - 1);root->right = _buildTree(preorder, inorder, i, x + 1, end);return root;};TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){int index = 0;//前序遍历数组第一个元素即根节点return _buildTree(preorder, inorder, index, 0, inorder.size() - 1);}
};

7.中序后序遍历序列构造二叉树

中序后序遍历序列构造二叉树

class Solution 
{
public:TreeNode* _buidTree(vector<int>& inorder, vector<int>& postorder, int& i,  int begin, int end){if (begin > end) return nullptr;int x = begin;for (x = begin; x <= end; ++x){if (inorder[x] == postorder[i])break;}TreeNode* root = new TreeNode(postorder[i--]);root->right = _buidTree(inorder, postorder, i, x + 1, end);root->left = _buidTree(inorder, postorder, i, begin, x - 1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int index = postorder.size() - 1;return _buidTree(inorder, postorder, index, 0, inorder.size() - 1);}
};

8.二叉树的前序遍历【非递归】

二叉树的前序遍历

vector<int> preorderTraversal(TreeNode* root)
{vector<int> v;       //v存储遍历的数据stack<TreeNode*> st; //利用栈的特点 调整读取数据的顺序存入到v中TreeNode* cp = root;while (cp || !st.empty()){//左路结点while (cp){v.push_back(cp->val);st.push(cp);cp = cp->left;}//左路结点的右子树TreeNode* top = st.top();cp = top->right;st.pop();}return v;
}

9.二叉树的中序遍历【非递归】

二叉树的中序遍历

vector<int> inorderTraversal(TreeNode* root) 
{vector<int> v;stack<TreeNode*> st;TreeNode* cp = root;while (cp || !st.empty())   {while (cp){st.push(cp);cp = cp->left;}TreeNode* top = st.top();v.push_back(top->val);cp = top->right;st.pop();}return v;
};

10.二叉树的后序遍历【非递归】

二叉树的后序遍历

1.法一：栈模拟实现递归

vector<int> postorderTraversal(TreeNode* root)
{vector<int> v;stack<TreeNode*> st;TreeNode* cp = root;TreeNode* prv = nullptr;while (cp || !st.empty()){while (cp){st.push(cp);cp = cp->left;}TreeNode* top = st.top();if (top->right == nullptr || top->right == prv){v.push_back(top->val);prv = top;st.pop();}else{cp = top->right;}}return v;
};

2.法二：前序遍历修改

class Solution 
{
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;st.push(root);while (!st.empty()){TreeNode* top = st.top();st.pop();if (top)v.push_back(top->val);elsecontinue;st.push(top->left);st.push(top->right);}reverse(v.begin(), v.end());return v;}
};