题目

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:

1 2	10 1 2 3 4 5 6 7 8 9 0

Sample Output:

1	6 3 8 1 5 7 9 0 2 4

题解

思路

首先抓到题目的重点
要将序列构造出一个完全BST
那么BST的特点是什么呢?
左小右大
这样的特点就导致了一个遍历的特点
就是中序的时候是从小到大的
那么我们对原序列排序，即可得到中序遍历
题目要求我们输出层次遍历
所以题目意思变为中序转层序
我们可以写一个递归完成这一点。
用一个level记录层数，传递来的是一棵树的left和right，我们找到这棵数的根，然后递归进入左子树和右子树。用ans记录节点和层数。

def count_level(left_begin, right_end, level):
    if left_begin > right_end:
        return
    root = # 还不知道
    ans.append([nodes[root], level])
    count_level(left_begin, root - 1, level + 1)
    count_level(root + 1, right_end, level + 1)
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">+ 因为我们总是先左后右，所以排完序同一层里也是先左后右。</span><br><span class="line"></span><br><span class="line">+ 那么一开始传递的就是&#96;count_level(0,len(nodes)-1,0)&#96;</span><br><span class="line"></span><br><span class="line">+ 最后再排序输出就可以了。</span><br><span class="line"></span><br><span class="line">+ 问题是root该怎么找？</span><br><span class="line"></span><br><span class="line">+ 如果二叉树是满二叉数，即最后一行是填满的，那么我们的中间值就是&#96;(right_end + left_begin + 1) &#x2F;&#x2F; 2&#96;。</span><br><span class="line"></span><br><span class="line">+ 但是问题是我们的左侧二叉树不一定是满的。</span><br><span class="line"></span><br><span class="line">+ 所以我们计算这棵树最深到了哪一层，并假设这一层填满，这样采用同样的式子计算中间位置就OK了。</span><br><span class="line"></span><br><span class="line">+ &#96;right_end - left_begin + 1&#96; 是这棵树的节点数量，记作&#96;num_nodes&#96;</span><br><span class="line"></span><br><span class="line">+ 当节点数量为1的时候，就1层</span><br><span class="line"></span><br><span class="line">+ 当节点数量在2到3的时候，2层</span><br><span class="line"></span><br><span class="line">+ 当节点数量在4到7的时候，3层</span><br><span class="line"></span><br><span class="line">+ 当节点数量在8到15的时候，4层</span><br><span class="line"></span><br><span class="line">+ 所以我们的节点数量+1取2的对数的下顶，即是这棵树被填满的总层数，记作&#96;filled_levels&#96;</span><br><span class="line"></span><br><span class="line">+ 而以2为底，以层数为指数，这样的&#96;2^level - 1&#96;就是这棵树被填满的总层数所容纳的总节点数，记作&#96;filled_nodes&#96;。</span><br><span class="line"></span><br><span class="line">+ 回到我们的例子</span><br><span class="line"></span><br><span class="line">+ &#96;&#96;&#96;</span><br><span class="line">  									6</span><br><span class="line">  						3							8</span><br><span class="line">  			1					5			7				9</span><br><span class="line">  		0		2			4			</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

我们的root的索引如何找到？
首先我们不算最后三个，先看被填满的部分。

				6
		3					8
	1		5			7		9	
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">+ 在这里，我们的根节点的索引应该是3</span><br><span class="line"></span><br><span class="line">+ 就是&#96;left_begin + (filled_nodes - 1) &#x2F;&#x2F; 2&#96;，左边的left_begin是基数，它要再加上所有数的一半，这个位置便是我们想要的位置。</span><br><span class="line"></span><br><span class="line">+ 那么我们后面还剩&#96;num_nodes - filled_nodes&#96;，我们的root再加上它，即可。</span><br><span class="line"></span><br><span class="line">+ 注意！这只是针对题目里的情况，如果&#96;num_nodes - filled_nodes&#96;超过了没填满的那一层的一半，这说明&#96;num_nodes - filled_nodes&#96;的一部分其实是在右子树当中的。于是更严谨地，我们再加上的应该是</span><br><span class="line"></span><br><span class="line">+ &#96;min(num_nodes - filled_nodes, (filled_nodes + 1) &#x2F;&#x2F; 2)&#96;后者是最后未填满的一层总容量的一半。</span><br><span class="line"></span><br><span class="line">## 数据结构</span><br><span class="line"></span><br><span class="line">+ nodes 保存原来的节点</span><br><span class="line">+ ans是一个列表，保存我们的答案</span><br><span class="line">  + 一个节点是一个列表，包含节点值和层数</span><br><span class="line"></span><br><span class="line">## 算法</span><br><span class="line"></span><br><span class="line">+ 都写在思路里了。</span><br><span class="line"></span><br><span class="line">## 代码</span><br><span class="line"></span><br><span class="line">+ 因为使用Python3 能AC，因此只放了Python3的代码。</span><br><span class="line"></span><br><span class="line">&#96;&#96;&#96;python</span><br><span class="line">from math import floor, log2</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">def count_level(left_begin, right_end, level):</span><br><span class="line">    if left_begin &gt; right_end:</span><br><span class="line">        return</span><br><span class="line">    if left_begin &#x3D;&#x3D; right_end:</span><br><span class="line">        ans.append([nodes[left_begin], level])</span><br><span class="line">        return</span><br><span class="line">    num_nodes &#x3D; right_end - left_begin + 1</span><br><span class="line">    filled_nodes &#x3D; pow(2, floor(log2(num_nodes))) - 1</span><br><span class="line">    root &#x3D; left_begin + (filled_nodes - 1) &#x2F;&#x2F; 2 + min(num_nodes - filled_nodes, (filled_nodes + 1) &#x2F;&#x2F; 2)</span><br><span class="line">    ans.append([nodes[root], level])</span><br><span class="line">    count_level(left_begin, root - 1, level + 1)</span><br><span class="line">    count_level(root + 1, right_end, level + 1)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">_ &#x3D; input()</span><br><span class="line">nodes &#x3D; sorted(list(map(int, input().split())))</span><br><span class="line">ans &#x3D; []</span><br><span class="line">count_level(0, len(nodes) - 1, 0)</span><br><span class="line">ans.sort(key&#x3D;lambda x: x[1])</span><br><span class="line">print(&quot; &quot;.join(list(map(str, [i[0] for i in ans]))))</span><br><span class="line"></span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->