<navid="article-nav">

<ahref="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/"id="article-nav-newer"class="article-nav-link-wrap">

<iclass="icon-circle-left"></i>

<divclass="article-nav-title">

1119 Pre- and Post-order Traversals (30分)

<ahref="/2020/03/04/1064%20Complete%20Binary%20Search%20Tree%20(30%E5%88%86)/"id="article-nav-older"class="article-nav-link-wrap">

<divclass="article-nav-title">1064 Complete Binary Search Tree (30分)</div>

<divclass="archives">

<articleclass="archive-article archive-type-post">

<divclass="archive-article-inner">

<headerclass="archive-article-header">

<divclass="article-meta">

<ahref="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/"class="archive-article-date">

<timedatetime="2020-03-05T14:17:04.357Z"itemprop="datePublished"><iclass="icon-calendar icon"></i>2020-03-05</time>

<h1itemprop="name">

<aclass="archive-article-title"href="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/">1119 Pre- and Post-order Traversals (30分)</a>

<divclass="article-info info-on-right">

<divclass="clearfix"></div>

<articleclass="archive-article archive-type-post">

<divclass="archive-article-inner">

<headerclass="archive-article-header">

<divclass="archives">

<articleclass="archive-article archive-type-post">

<divclass="archive-article-inner">

<headerclass="archive-article-header">

<divclass="article-meta">

<ahref="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/"class="archive-article-date">

<timedatetime="2020-03-05T14:17:04.357Z"itemprop="datePublished"><iclass="icon-calendar icon"></i>2020-03-05</time>

<h1itemprop="name">

<aclass="archive-article-title"href="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/">1119 Pre- and Post-order Traversals (30分)</a>

<divclass="article-info info-on-right">

<divclass="clearfix"></div>

<articleclass="archive-article archive-type-post">

<divclass="archive-article-inner">

<headerclass="archive-article-header">

<divclass="archives">

<articleclass="archive-article archive-type-post">

<divclass="archive-article-inner">

<headerclass="archive-article-header">

<divclass="article-meta">

<ahref="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/"class="archive-article-date">

<timedatetime="2020-03-05T14:17:04.357Z"itemprop="datePublished"><iclass="icon-calendar icon"></i>2020-03-05</time>

<h1itemprop="name">

<aclass="archive-article-title"href="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/">1119 Pre- and Post-order Traversals (30分)</a>

<divclass="article-info info-on-right">

<divclass="clearfix"></div>

<articleclass="archive-article archive-type-post">

<divclass="archive-article-inner">

<headerclass="archive-article-header">

[{"title":"bean的生命周期","date":"2020-03-05T07:34:39.139Z","path":"2020/03/05/bean的生命周期/","tags":[]},{"title":"1064 Complete Binary Search Tree (30分)","date":"2020-03-04T01:31:02.291Z","path":"2020/03/04/1064 Complete Binary Search Tree (30分)/","tags":[]},{"title":"1094 The Largest Generation (25分)","date":"2020-03-02T03:50:29.787Z","path":"2020/03/02/1094 The Largest Generation (25分)/","tags":[]},{"title":"My First Post","date":"2020-01-22T12:59:37.000Z","path":"2020/01/22/My-First-Post/","tags":[]},{"title":"Hello World","date":"2020-01-22T07:52:45.957Z","path":"2020/01/22/hello-world/","tags":[]}]

[{"title":"1119 Pre- and Post-order Traversals (30分)","date":"2020-03-05T14:17:04.357Z","path":"2020/03/05/1119 Pre- and Post-order Traversals (30分)/","tags":[]},{"title":"bean的生命周期","date":"2020-03-05T07:34:39.139Z","path":"2020/03/05/bean的生命周期/","tags":[]},{"title":"1064 Complete Binary Search Tree (30分)","date":"2020-03-04T01:31:02.291Z","path":"2020/03/04/1064 Complete Binary Search Tree (30分)/","tags":[]},{"title":"1094 The Largest Generation (25分)","date":"2020-03-02T03:50:29.787Z","path":"2020/03/02/1094 The Largest Generation (25分)/","tags":[]},{"title":"My First Post","date":"2020-01-22T12:59:37.000Z","path":"2020/01/22/My-First-Post/","tags":[]},{"title":"Hello World","date":"2020-01-22T07:52:45.957Z","path":"2020/01/22/hello-world/","tags":[]}]

<divid="js-content"class="content-ll">

<articleid="post-1119 Pre- and Post-order Traversals (30分)"class="article article-type-post article-index"itemscopeitemprop="blogPost">

<divclass="article-inner">

<headerclass="article-header">

<h1itemprop="name">

<aclass="article-title"href="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/">1119 Pre- and Post-order Traversals (30分)</a>

<ahref="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/"class="archive-article-date">

<timedatetime="2020-03-05T14:17:04.357Z"itemprop="datePublished"><iclass="icon-calendar icon"></i>2020-03-05</time>

<divclass="article-entry"itemprop="articleBody">

<p>题目大意：给出一棵树的结点个数n，以及它的前序遍历和后序遍历，输出它的中序遍历，如果中序遍历不唯一就输出No，且输出其中一个中序即可，如果中序遍历唯一就输出Yes，并输出它的中序</p>

<p>主要是如何判断结果是否唯一，已知二叉树的前序和后序是无法唯一确定一颗二叉树的，因为可能会存在多种情况。当只有一个孩子节点的时候，无法判断这个孩子节点是左孩子还是右孩子</p>

<p>先查看中序遍历是否唯一，先序遍历顺序为：根左右，后序遍历顺序为：左右根，那么如果一个节点只包含左子节点或者只包含右子节点，但是根据上面的顺序可以发现，他们的先序遍历和后续遍历是没有发生变化的，例如：</p>

<p><imgsrc="https://i.loli.net/2020/03/05/HOCzKonSWIEtUf5.png"alt="20190301161354433.png">)<imgsrc="https://i.loli.net/2020/03/05/HOCzKonSWIEtUf5.png"alt="20190301161354433.png">)<imgsrc="https://i.loli.net/2020/03/05/HOCzKonSWIEtUf5.png"alt="20190301161354433.png"></p>

<p>此图中节点1，节点3，只含有左子节点或者右子节点，但是他们的先序遍历和后续遍历都是相同的：</p>

<p>先序遍历：1 2 5 3 4</p>

<p>后序遍历：5 4 3 2 1</p>

<p><strong>所以只要父亲节点只包含一个子节点，那么这个答案就是不唯一的</strong></p>

<p>后序遍历和先序遍历得到中序遍历（例一为例）</p>

<p><imgsrc="https://i.loli.net/2020/03/05/jFwO1GVPpbNIHzu.png"alt="20190301162154255.png"></p>

<p>先序遍历： 1 2 3 4 6 7 5 后序遍历： 2 6 7 4 5 3 1</p>

<p>在先序遍历中先取出开始的节点1，这个节点定为当前根节点，1后面一个节点2一定是节点1的一个子节点，然后在后序遍历中寻找节点2，于是便可知节点2（包括2）之前的位于节点1的左子树中，2（不包括2）后面的节点直至节点1，位于节点1的右子树</p>

<p>节点2 3 6 7 5位于节点1的右子树中，根据先序遍历可知3为这个子树的根节点，节点4为节点3的左或右子节点中的一个，后序遍历中找到节点4，可以知道节点6 7 4位于节点3的左子树中，节点5位于节点3的右子树中</p>

<p>依次类推，可以遍历完这棵树，于是便可得到中序遍历</p>

<p>如果上述中找到只包含一个子节点的父节点，没有发现另外一个节点，<strong>即当前遍历区间中只包含当前节点的一个子节点</strong>，说明这个树是不唯一的，我们默认情况下将其安排在左子节点中</p>

<figureclass="highlight c++"><table><tr><tdclass="gutter"><pre><spanclass="line">1</span><br><spanclass="line">2</span><br><spanclass="line">3</span><br><spanclass="line">4</span><br><spanclass="line">5</span><br><spanclass="line">6</span><br><spanclass="line">7</span><br><spanclass="line">8</span><br><spanclass="line">9</span><br><spanclass="line">10</span><br><spanclass="line">11</span><br><spanclass="line">12</span><br><spanclass="line">13</span><br><spanclass="line">14</span><br><spanclass="line">15</span><br><spanclass="line">16</span><br><spanclass="line">17</span><br><spanclass="line">18</span><br><spanclass="line">19</span><br><spanclass="line">20</span><br><spanclass="line">21</span><br><spanclass="line">22</span><br><spanclass="line">23</span><br><spanclass="line">24</span><br><spanclass="line">25</span><br><spanclass="line">26</span><br><spanclass="line">27</span><br><spanclass="line">28</span><br><spanclass="line">29</span><br><spanclass="line">30</span><br><spanclass="line">31</span><br><spanclass="line">32</span><br><spanclass="line">33</span><br><spanclass="line">34</span><br><spanclass="line">35</span><br><spanclass="line">36</span><br><spanclass="line">37</span><br><spanclass="line">38</span><br><spanclass="line">39</span><br><spanclass="line">40</span><br><spanclass="line">41</span><br><spanclass="line">42</span><br><spanclass="line">43</span><br><spanclass="line">44</span><br><spanclass="line">45</span><br></pre></td><tdclass="code"><pre><spanclass="line"><spanclass="meta">#<spanclass="meta-keyword">include</span><spanclass="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><spanclass="line"><spanclass="keyword">using</span><spanclass="keyword">namespace</span><spanclass="built_in">std</span>;</span><br><spanclass="line"><spanclass="keyword">const</span><spanclass="keyword">int</span> maxn =<spanclass="number">30</span> +<spanclass="number">10</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">int</span> pre[maxn], post[maxn];</span><br><spanclass="line"><spanclass="built_in">vector</span>&lt;<spanclass="keyword">int</span>&gt; in;</span><br><spanclass="line"><spanclass="keyword">bool</span> flag;</span><br><spanclass="line"><spanclass="function"><spanclass="keyword">void</span><spanclass="title">in_order</span><spanclass="params">(<spanclass="keyword">int</span> preLeft,<spanclass="keyword">int</span> preRight,<spanclass="keyword">int</span> postLeft,<spanclass="keyword">int</span> postRight)</span></span>&#123;</span><br><spanclass="line"><spanclass="keyword">if</span> (preLeft == preRight) &#123;</span><br><spanclass="line">in.push_back(pre[preLeft]);</span><br><spanclass="line"><spanclass="keyword">return</span>;</span><br><spanclass="line">&#125;</span><br><spanclass="line"><spanclass="keyword">if</span> (pre[preLeft] == post[postRight]) &#123;</span><br><spanclass="line"><spanclass="keyword">int</span> i = preLeft +<spanclass="number">1</span>;</span><br><spanclass="line"><spanclass="keyword">while</span> (i &lt;= preRight &amp;&amp; pre[i] != post[postRight -<spanclass="number">1</span>])</span><br><spanclass="line">i++;</span><br><spanclass="line"><spanclass="keyword">if</span> (i - preLeft &gt;<spanclass="number">1</span>)<spanclass="comment">//父节点有两个子节点，结构唯一</span></span><br><spanclass="line">in_order(preLeft +<spanclass="number">1</span>, i -<spanclass="number">1</span>, postLeft, postLeft + (i - preLeft -<spanclass="number">1</span>) -<spanclass="number">1</span>);<spanclass="comment">//左子树</span></span><br><spanclass="line"><spanclass="keyword">else</span><spanclass="keyword">if</span> (i - preLeft ==<spanclass="number">1</span>)<spanclass="comment">//父节点有一个子节点，则可左可右，结构不唯一</span></span><br><spanclass="line">flag =<spanclass="literal">false</span>;</span><br><spanclass="line">in.push_back(pre[preLeft]);<spanclass="comment">//根节点</span></span><br><spanclass="line">in_order(i, preRight, postLeft + (i - preLeft -<spanclass="number">1</span>), postRight -<spanclass="number">1</span>);<spanclass="comment">//右子树</span></span><br><spanclass="line">&#125;</span><br><spanclass="line">&#125;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="function"><spanclass="keyword">int</span><spanclass="title">main</span><spanclass="params">(<spanclass="keyword">int</span> argc,<spanclass="keyword">char</span><spanclass="keyword">const</span> *argv[])</span></span></span><br><spanclass="line"><spanclass="function"></span>&#123;</span><br><spanclass="line"><spanclass="keyword">int</span> N, i;</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; N;</span><br><spanclass="line"><spanclass="keyword">for</span> (<spanclass="keyword">int</span> i =<spanclass="number">0</span>; i &lt; N; ++i)</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; pre[i];</span><br><spanclass="line"><spanclass="keyword">for</span> (<spanclass="keyword">int</span> i =<spanclass="number">0</span>; i &lt; N; ++i)</span><br><spanclass="line"><spanclass="built_in">cin</span> &gt;&gt; post[i];</span><br><spanclass="line">flag =<spanclass="literal">true</span>;</span><br><spanclass="line">in_order(<spanclass="number">0</span>, N -<spanclass="number">1</span>,<spanclass="number">0</span>, N -<spanclass="number">1</span>);</span><br><spanclass="line"><spanclass="keyword">if</span> (flag)</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt;<spanclass="string">"Yes"</span> &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"><spanclass="keyword">else</span></span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt;<spanclass="string">"No"</span> &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"><spanclass="keyword">for</span> (i =<spanclass="number">0</span>; i &lt; N -<spanclass="number">1</span>; ++i)</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; in[i] &lt;&lt;<spanclass="string">" "</span>;</span><br><spanclass="line"><spanclass="built_in">cout</span> &lt;&lt; in[i] &lt;&lt;<spanclass="built_in">endl</span>;</span><br><spanclass="line"></span><br><spanclass="line"><spanclass="keyword">return</span><spanclass="number">0</span>;</span><br><spanclass="line">&#125;</span><br></pre></td></tr></table></figure>

<divclass="article-info article-info-index">

<pclass="article-more-link">

<aclass="article-more-a"href="/2020/03/05/1119%20Pre-%20and%20Post-order%20Traversals%20(30%E5%88%86)/">展开全文>></a>

<divclass="clearfix"></div>

<asideclass="wrap-side-operation">

<divclass="mod-side-operation">

<divclass="jump-container"id="js-jump-container"style="display:none;">

<ahref="#"diff-0eb547304658805aad788d320f10bf1f292797b5e6d745a3bf617584da017051-173-237-0" data-selected="false" role="gridcell" tabindex="-1" valign="top">

<iclass="icon-font icon-back"></i>

<divid="js-jump-plan-container"class="jump-plan-container"style="top: -11px;">

<iclass="icon-font icon-plane jump-plane"></i>

<articleid="post-bean的生命周期"class="article article-type-post article-index"itemscopeitemprop="blogPost">

<divclass="article-inner">