二叉搜索树序列

骑猪看日落 2023-02-10 03:47 3阅读 0赞

## 一、前言 ##

里面来源LeetCode，难度：困难

问题链接：[https://leetcode-cn.com/problems/bst-sequences-lcci/][https_leetcode-cn.com_problems_bst-sequences-lcci]

## 二、题目 ##

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉树，输出所有可能生成此树的数组。

示例:

给定如下二叉树
            2
           / \
          1   3
    返回:
    [
       [2,1,3],
       [2,3,1]
    ]

## 三、题意分析 ##

本题的题意为：“根结点的数值” 总是先于它的 “左右子树中的结点的数值” 被插入树中。父节点优先级最高需要最先读取，左右子结点优先级相同，当左结点（或右结点）被读取之后，它的左右子结点和它服叔结点是同同一优先级，都可以在下次被读取。

例如树：

![2020051921410393.png][]

1）根节点4最先读取，2和5都可以在下次中被读取，

2）若第二次读取的是结点2，则1 3 5在接下来都可以被读取，对1 3 5 全排序有6种情况（135,153,315,351,513,531）。

3）若第二次读取的是结点5，则1 3在接下来都可以被读取，对1 3 全排序有2种情况（13,31）。

可能生成此树的数组有8个：

1> 4，2，1，3，5

2> 4，2，1，5，3

3> 4，2，3，1，5

4> 4，2，3，5，1

5> 4，2，5，1，3

6> 4，2，5，3，1

7> 4，5，2，1，3

8> 4，5，2，3，1

第一次看题，将其理解成先读父节点，再读左或者右节点。实现代码见——**5.1 错误理解实现代码**。

## 四、思路 ##

用队列来获得当前可以读取的结点，然后对可以读取结点进行全排序，当读完一个结点的时候，可能会有新的结点新增。我们先看看怎样用队列实现全排序代码见——**5.2 用队列实现的全排序**，这里的全排序是对固定元素进行全排序。《二叉搜索树序列》中在全排序过程中可能会新增新的元素（子结点），实现代码见——**5.3 最终解决方案**，理解了用队列实现全排序，这个问题也就好理解了。

全排序另外一种解法：[https://blog.csdn.net/nie2314550441/article/details/105670259][https_blog.csdn.net_nie2314550441_article_details_105670259]

## 五、编码实现 ##

### 5.1 错误理解实现代码: ###

template<class T>
    vector<vector<T>> BSTSequences_ERROR(BinaryTreeNode<T>* root)
    {
    	vector<vector<T>> result;
    	if (root == nullptr)
    	{
    		return result;
    	}
    
    	vector<vector<T>> l = BSTSequences_ERROR(root->m_pLeft);
    	vector<vector<T>> r = BSTSequences_ERROR(root->m_pRight);
    
    	vector<T> t;
    	if (l.empty() || r.empty())
    	{
    		t.push_back(root->m_nValue);
    		result.push_back(t);
    		return result;
    	}
    
    	for (auto itl = l.begin(); itl != l.end(); ++itl)
    	{
    		for (auto itr = r.begin(); itr != r.end(); ++itr)
    		{
    			t.clear();
    			t.push_back(root->m_nValue);
    			t.insert(t.end(), itl->begin(), itl->end());
    			t.insert(t.end(), itr->begin(), itr->end());
    			result.push_back(t);
    
    			t.clear();
    			t.push_back(root->m_nValue);
    			t.insert(t.end(), itr->begin(), itr->end());
    			t.insert(t.end(), itl->begin(), itl->end());
    
    			result.push_back(t);
    		}
    	}
    
    	return result;
    }

###  ###

### 5.2 用队列实现的全排序 ###

// 队列实现全排序
    void Permutation_Inner(deque<char>& q, vector<char>& buf, vector<vector<char> >& ans);
    
    void Permutation(char* pStr)
    {
    	if (pStr == nullptr)
    		return;
    
    	deque<char> q;
    	int len = strlen(pStr);
    	for (int i = 0; i < len; ++i)
    	{
    		q.push_back(pStr[i]);
    	}
    
    	vector<char> buf;
    	vector<vector<char> > ans;
    	Permutation_Inner(q, buf, ans);
    }
    
    void Permutation_Inner(deque<char>& q, vector<char>& buf, vector<vector<char> >& ans)
    {
    	if (q.empty())
    	{
    		ans.push_back(buf);
    		return;
    	}
    
    	int size = (int)q.size();
    	const int len = (int)q.size();
    	while (size--)
    	{
    		char r = q.front(); q.pop_front();
    		buf.push_back(r);
    		int children = 0;
    
    		Permutation_Inner(q, buf, ans);
    		while (children--)
    		{
    			q.pop_back();
    		}
    
    		q.push_back(r);
    		buf.pop_back();
    	}
    }

###  ###

### 5.3 最终解决方案 ###

//==========================================================================
    /**
    * @file : BSTSequences.h
    * @title : 二叉搜索树序列
    * @purpose : 从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉树，输出所有可能生成此树的数组。
    *
    * 示例:
    * 给定如下二叉树
    *
    * 		2
    * 	   / \
    * 	  1   3
    *
    * 返回:
    * [
    *    [2,1,3],
    *    [2,3,1]
    * ]
    *
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/bst-sequences-lcci/
    */
    //==========================================================================
    
    #pragma once
    #include <iostream>
    #include <vector>
    #include "Common.h"
    #include "ConstructTree.h"
    
    using namespace std;
    
    template<class T>
    void BSTSequences_Inner(deque<BinaryTreeNode<T>*>& q, vector<T>& buf, vector<vector<T> >& ans);
    
    template<class T>
    vector<vector<T>> BSTSequences(BinaryTreeNode<T>* root)
    {
    	if (!root) return { {} };
    
    	deque<BinaryTreeNode<T>*> q;
    	q.push_back(root);
    	vector<T> buf;
    	vector<vector<T> > ans;
    	BSTSequences_Inner(q, buf, ans);
    
    	return ans;
    }
    
    template<class T>
    void BSTSequences_Inner(deque<BinaryTreeNode<T>*>& q, vector<T>& buf, vector<vector<T> >& ans)
    {
    	if (q.empty())
    	{
    		ans.push_back(buf);
    		return;
    	}
    
    	int size = (int)q.size();
    	while (size--)
    	{
    		BinaryTreeNode<T>* r = q.front(); q.pop_front();
    		buf.push_back(r->m_nValue);
    		int children = 0;
    		if (r->m_pLeft)
    		{
    			++children;
    			q.push_back(r->m_pLeft);
    		}
    
    		if (r->m_pRight)
    		{
    			++children;
    			q.push_back(r->m_pRight);
    		}
    
    		BSTSequences_Inner(q, buf, ans);
    		while (children--)
    		{
    			q.pop_back();
    		}
    
    		q.push_back(r);
    		buf.pop_back();
    	}
    }
    
    // 以下为测试代码
    #define NAMESPACE_BSTSEQUENCES namespace NAME_BSTSEQUENCES {
    #define NAMESPACE_BSTSEQUENCESEND }
    
    //
    // 测试 用例 START
    NAMESPACE_BSTSEQUENCES
    
    template<class T>
    void test(const char* testName, BinaryTreeNode<T>* root, int expect)
    {
    	vector<vector<T>> result;
    	result = BSTSequences(root);
    	if (result.size() == expect)
    	{
    		cout << testName << " solution passed." << endl;
    	}
    	else
    	{
    		cout << testName << " solution failed." << result .size() << endl;
    	}
    }
    
    // 完全二叉树
    //              2
    //           /     \
    //          1      3  
    void Test1()
    {
    	const int length = 3;
    	int preorder[length] = { 2, 1, 3 };
    	int inorder[length] = { 1, 2, 3 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 2;
    
    	test("Test1()", pRoot, expect);
    }
    
    // 所有结点都没有右子结点
    //            5
    //           / 
    //          4   
    //         / 
    //        3 
    //       /
    //      2
    //     /
    //    1
    void Test2()
    {
    	const int length = 5;
    	char preorder[length + 1] = "54321";
    	char inorder[length + 1] = "12345";
    	char empty = ' ';
    
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 1;
    
    	test("Test2()", pRoot, expect);
    }
    
    // 完全二叉树
    //              4
    //           /     \
    //          2       5  
    //         / \    
    //        1   3   
    void Test3()
    {
    	const int length = 5;
    	int preorder[length] = { 4, 2, 1, 3, 5 };
    	int inorder[length] = { 1, 2, 3, 4, 5 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 8;
    
    
    
    	test("Test3()", pRoot, expect);
    }
    
    // 完全二叉树
    //              4
    //           /     \
    //          2       6  
    //         / \     / \
    //        1   3   5   7
    void Test4()
    {
    	const int length = 7;
    	int preorder[length] = { 4, 2, 1, 3, 6, 5, 7 };
    	int inorder[length] = { 1, 2, 3, 4, 5, 6, 7 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 80;
    
    	test("Test4()", pRoot, expect);
    }
    
    // 普通二叉树
    //              4
    //           /     \
    //          3       6 
    //         /       / \
    //        1       5   7
    //         \         /
    //          2       8
    void Test5()
    {
    	const int length = 8;
    	char preorder[length] = { 4, 3, 1, 2, 6, 5, 7, 8 };
    	char inorder[length] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 105;
    
    	test("Test5()", pRoot, expect);
    }
    
    NAMESPACE_BSTSEQUENCESEND
    // 测试 用例 END
    //
    
    void BSTSequences_Test()
    {
    	NAME_BSTSEQUENCES::Test1();
    	NAME_BSTSEQUENCES::Test2();
    	NAME_BSTSEQUENCES::Test3();
    	NAME_BSTSEQUENCES::Test4();
    	NAME_BSTSEQUENCES::Test5();
    }

**执行结果：**

![20200519214427469.png][]

[https_leetcode-cn.com_problems_bst-sequences-lcci]: https://leetcode-cn.com/problems/bst-sequences-lcci/
[2020051921410393.png]: https://img-blog.csdnimg.cn/2020051921410393.png
[https_blog.csdn.net_nie2314550441_article_details_105670259]: https://blog.csdn.net/nie2314550441/article/details/105670259
[20200519214427469.png]: https://img-blog.csdnimg.cn/20200519214427469.png