首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13200

树的偏斜度 对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题…

树的偏斜度

对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。

时间限制:1000

内存限制:65536

输入

输入在第一行给出正整数 n (≤ 103),为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列,键值为 1 到 n 的整数。同行数字间以空格分隔。

输出

在一行中按以下格式输出树的偏斜度: Ds = nL - nR


样例输入

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

样例输出

2 = 3 - 1
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std;   pair&lt;int, int&gt; calcSkew(vector&lt;int&gt;&amp; post, vector&lt;int&gt;&amp; in, int ps, int pe, int is, int ie) {     if (ps &gt; pe) return {0, 0};     int root = post[pe], idx = is;     while (in[idx] != root) idx++;     pair&lt;int, int&gt; left = calcSkew(post, in, ps, ps + idx - is - 1, is, idx - 1);     pair&lt;int, int&gt; right = calcSkew(post, in, ps + idx - is, pe - 1, idx + 1, ie);     return {left.first  + right.first  + (idx &gt; is &amp;&amp; idx == ie), left.second  + right.second  + (idx &lt; ie &amp;&amp; idx == is)}; }   int main() {     int n;     cin &gt;&gt; n;     vector&lt;int&gt; post(n), in(n);     for (int &amp;x : post) cin &gt;&gt; x;     for (int &amp;x : in) cin &gt;&gt; x;     pair&lt;int, int&gt; res = calcSkew(post, in, 0, n - 1, 0, n - 1);     cout &lt;&lt; res.first  - res.second  &lt;&lt; " = " &lt;&lt; res.first  &lt;&lt; " - " &lt;&lt; res.second  &lt;&lt; endl; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;unordered_map&gt; using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; TreeNode* buildTree(vector&lt;int&gt;&amp; inorder, vector&lt;int&gt;&amp; postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map&lt;int, int&gt;&amp; inMap) { if (inStart &gt; inEnd || postStart &gt; postEnd) return nullptr; int rootVal = postorder[postEnd]; TreeNode* root = new TreeNode(rootVal); int rootIndex = inMap[rootVal]; int leftSize = rootIndex - inStart; root-&gt;left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1, inMap); root-&gt;right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1, inMap); return root; } void countSkew(TreeNode* node, int&amp; nL, int&amp; nR) { if (!node) return; bool hasLeft = node-&gt;left != nullptr; bool hasRight = node-&gt;right != nullptr; if (hasLeft &amp;&amp; !hasRight) nL++; else if (!hasLeft &amp;&amp; hasRight) nR++; countSkew(node-&gt;left, nL, nR); countSkew(node-&gt;right, nL, nR); } int main() { int n; cin &gt;&gt; n; vector&lt;int&gt; post(n), in(n); for (int i = 0; i &lt; n; i++) cin &gt;&gt; post[i]; for (int i = 0; i &lt; n; i++) cin &gt;&gt; in[i]; unordered_map&lt;int, int&gt; inMap; for (int i = 0; i &lt; n; i++) inMap[in[i]] = i; TreeNode* root = buildTree(in, post, 0, n-1, 0, n-1, inMap); int nL = 0, nR = 0; countSkew(root, nL, nR); cout &lt;&lt; nL - nR &lt;&lt; " = " &lt;&lt; nL &lt;&lt; " - " &lt;&lt; nR &lt;&lt; endl; return 0; }</pre><p><br/></p>
这道题暂未补解析。