题目

Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 50,000), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the first number of the postorder traversal sequence of the corresponding binary tree.

Sample Input:

1
2
3

7
1 2 3 4 5 6 7
2 3 1 5 4 7 6

Sample Output:

题解

思路

题目给出了前序遍历和中序遍历
求后序遍历的第一个数
前序遍历是根左右
中序遍历是左根右
后序遍历是左右根
我们可以这样画图来辅助理解，对于一棵树或子树，都符合下面的规律

前序：  根[    左    ][    右    ]
中序：  [    左    ]根[    右    ]
<!--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></pre></td><td class="code"><pre><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"></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">+ pre 是前序序列</span><br><span class="line">+ in 是中序序列</span><br><span class="line">+ judge 是递归函数</span><br><span class="line">+ pre_left 是在前序中的树的左边界</span><br><span class="line">+ in_left,in_right 是在中序中的树的左右边界</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">+ 由于这道题测试数据格式有误，Python有一个点会非零返回。</span><br><span class="line"></span><br><span class="line">### Python 3</span><br><span class="line"></span><br><span class="line">&#96;&#96;&#96;python</span><br><span class="line">def judge(pre_left, in_left, in_right):</span><br><span class="line">    in_root &#x3D; _in.index(pre[pre_left])</span><br><span class="line">    if in_left &lt;&#x3D; in_root - 1:</span><br><span class="line">        judge(pre_left + 1, in_left, in_root - 1)</span><br><span class="line">    elif in_root + 1 &lt;&#x3D; in_right:</span><br><span class="line">        judge(pre_left + (in_root - in_left) + 1, in_root + 1, in_right)</span><br><span class="line">    else:</span><br><span class="line">        print(_in[in_root])</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">n &#x3D; int(input())</span><br><span class="line">pre &#x3D; list(map(int, input().split()))</span><br><span class="line">_in &#x3D; list(map(int, input().split()))</span><br><span class="line">judge(0, 0, n - 1)</span><br><span class="line"></span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>

using namespace std;
void judge(const int pre[],const int in[],int pre_left,int in_left,int in_right){
    int in_root;
    for (int i = in_left;i<=in_right;++i){
        if (in[i] == pre[pre_left]){
            in_root = i;
            break;
        }
    }
    if (in_left <= in_root - 1)
        judge(pre,in,pre_left + 1, in_left, in_root - 1);
    else if(in_root + 1 <= in_right)
        judge(pre,in,pre_left + (in_root - in_left) + 1, in_root + 1, in_right);
    else
        cout<<in[in_root]<<endl;

}

int main() {
    int n;
    cin >> n;
    int pre[n];
    int in[n];
    for (int i = 0; i < n; i++)
        cin >> pre[i];
    for (int i = 0; i < n; i++)
        cin >> in[i];
    judge(pre,in,0,0,n-1);
}