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

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;
	}
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

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;
	}
};



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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其中一个是根 那么根就为obj
		if (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为obj
		if ((pInLeft && qInRight) || (pInRight && qInLeft))
			return root;
		//均左==》递归到左子树
		if (pInLeft && qInLeft)
			return lowestCommonAncestor(root->left, p, q);
		//均右==》递归到右子树
		else
			return lowestCommonAncestor(root->right, p, q);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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();
			else
				qRoute.pop();
		}
		while (pRoute.top() != qRoute.top())
		{
			pRoute.pop();
			qRoute.pop();
		}
		return pRoute.top();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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;
		//更新prv
		prv = 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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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];
	}

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

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);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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);
			else
				continue;
			st.push(top->left);
			st.push(top->right);
		}
        reverse(v.begin(), v.end());
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24