(200分)- 二叉树计算Java JS Python C题目描述给出一个二叉树如下图所示请由该二叉树生成一个新的二叉树它满足其树中的每个节点将包含原始树中的左子树和右子树的和。左子树表示该节点左侧叶子节点为根节点的一颗新树右子树表示该节点右侧叶子节点为根节点的一颗新树。输入描述2行整数第1行表示二叉树的中序遍历第2行表示二叉树的前序遍历以空格分割例如7 -2 6 6 96 7 -2 9 6输出描述1行整数表示求和树的中序遍历以空格分割例如-2 0 20 0 6用例输入-3 12 6 8 9 -10 -78 12 -3 6 -10 9 -7输出0 3 0 7 0 2 0说明无题目解析本题考察二叉树的中序遍历、前序遍历以及根据这两种遍历序列重建二叉树的方法。中序遍历遵循左根右顺序先遍历左子树再访问根节点最后遍历右子树。 前序遍历采用根左右顺序先访问根节点再遍历左子树最后遍历右子树。在前序遍历序列中第一个元素即为根节点。例如题目给出的前序遍历序列 6 7 -2 9 6 其中首元素6就是根节点。确定根节点后需在中序遍历序列中定位该节点。题目中的中序遍历序列为 7 -2 6 6 9 这里存在两个值为6的节点需要分别验证若选择第一个6红色标记作为根节点根据中序左根右规则左子树中序序列为7 -2右子树中序序列为6 9若选择第二个6绿色标记作为根节点左子树中序序列为7 -2 6右子树中序序列为9通过中序遍历可以确定左右子树的长度。由于同一棵子树的中序和前序遍历序列长度相同我们可以据此在前序遍历中划分左右子树的范围。例如当选择第一个6作为根节点时左子树7 -2长度为2右子树6 9长度为2 这样就可以在前序遍历序列中对应划分出左右子树的范围。此时对比前序的左子树和中序的左子树是否节点相同对比前序的右子树和中序的右子树是否相同如果左右子树都一致则当前根是正确根。如果我们选错根比如选中序遍历序列中第二个6作为根则通过对比可以发现中序遍历和前序遍历的左右子树划分方式存在差异。具体来说我们可以按照以下步骤进行验证前序遍历的首元素即为二叉树的根节点值在中序遍历序列中定位该根节点值的位置根据该位置划分出左子树和右子树的长度范围分别在前序和中序序列中提取对应的子树序列进行比对 若序列一致则说明中序序列中的根节点位置正确反之则存在错误。在代码实现中我们通过buildTree函数完成二叉树的还原工作详见代码注释。该函数的构建逻辑与上述验证步骤完全一致。此外题目要求基于原始二叉树构建新树新树中每个节点的值等于其左右子树所有节点值之和。为此我们在TreeNode结构体中新增了childSum属性用于记录子树节点值之和。这样在递归构建原始树的过程中就能同步完成childSum值的计算。最终输出新树的中序遍历序列具体实现参见代码中的getMidOrder函数。JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { // 中序遍历序列 const midOrder (await readline()).split( ).map(Number); // 前序遍历序列 const preOrder (await readline()).split( ).map(Number); const n midOrder.length; // 记录中序遍历序列中序列元素值所在位置本题中可能存在重复元素因此某个序列元素值可能有多个位置 const midIndexMap {}; for (let i 0; i n; i) { const num midOrder[i]; if (!midIndexMap[num]) { midIndexMap[num] []; } midIndexMap[num].push(i); } class TreeNode { constructor(num) { this.num num; // 当前节点的值 this.childSum 0; // 当前节点的左子树右子树的和 this.leftChild null; this.rightChild null; } } /** * 判断两个子数组是否相同元素相同顺序可以不同 * param {*} midL 子数组1的左边界 * param {*} preL 子数组2的左边界 * param {*} size 子数组的长度 * returns 子数组1和子数组2是否相同 */ function notEquals(midL, preL, size) { const arr1 midOrder.slice(midL, midL size).sort(); const arr2 preOrder.slice(preL, preL size).sort(); for (let i 0; i size; i) { if (arr1[i] ! arr2[i]) { return true; } } return false; } /** * 根据中序遍历序列、前序遍历序列还原树结构 * param {*} midL 中序遍历子序列的左边界 * param {*} midR 中序遍历子序列的右边界 * param {*} preL 前序遍历子序列的左边界 * param {*} preR 前序遍历子序列的右边界 * returns 树结构的根节点 */ function buildTree(midL, midR, preL, preR) { // 某个节点子树对应一段子序列如果对应子序列范围不存在则子树也不存在 if (preL preR) return null; // 先根据前序遍历序列得到根节点前序序列的首元素就是根节点 const rootNum preOrder[preL]; const root new TreeNode(rootNum); // 在中序遍历序列中找到对应根值的位置这个位置可能有多个但是只有一个是正确的 for (let idx of midIndexMap[rootNum]) { // 如果对应根值位置越界则不是正确的 if (idx midL || idx midR) continue; // 如果中序的左子树和前序的左子树不同则对应根值位置不正确 const leftLen idx - midL; if (notEquals(midL, preL 1, leftLen)) continue; // 如果中序的右子树和前序的右子树不同则对应根值位置不正确 const rightLen midR - idx; if (notEquals(idx 1, preR - rightLen 1, rightLen)) continue; // 找到正确根值位置后开始分治递归处理左子树和右子树 root.leftChild buildTree(midL, idx - 1, preL 1, preL leftLen); root.rightChild buildTree(idx 1, midR, preR - rightLen 1, preR); // 记录该节点左子树右子树的和本题新二叉树节点的值 root.childSum (root.leftChild null ? 0 : root.leftChild.num root.leftChild.childSum) (root.rightChild null ? 0 : root.rightChild.num root.rightChild.childSum); break; } return root; } // 二叉树中序遍历 function getMidOrder(root, res) { if (root null) return; // 先遍历左子树 const leftChild root.leftChild; if (leftChild ! null) { getMidOrder(leftChild, res); } // 再遍历根 res.push(root.childSum); // 最后遍历右子树 const rightChild root.rightChild; if (rightChild ! null) { getMidOrder(rightChild, res); } } // 根据中序序列和前序序列还原树结构 const root buildTree(0, n - 1, 0, n - 1); // 记录新的二叉树的的中序遍历序列 const res []; getMidOrder(root, res); console.log(res.join( )); })();Java算法源码import java.util.*; public class Main { static class TreeNode { int num; // 当前节点的值 int childSum; // 当前节点的左子树右子树的和 TreeNode leftChild; TreeNode rightChild; public TreeNode(int num) { this.num num; this.childSum 0; this.leftChild null; this.rightChild null; } } // 中序遍历序列 static int[] midOrder; // 前序遍历序列 static int[] preOrder; // 记录中序遍历序列中序列元素值所在位置本题中可能存在重复元素因此某个序列元素值可能有多个位置 static HashMapInteger, ArrayListInteger midIndexMap new HashMap(); public static void main(String[] args) { Scanner sc new Scanner(System.in); midOrder Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray(); preOrder Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray(); int n midOrder.length; for (int i 0; i n; i) { int num midOrder[i]; midIndexMap.putIfAbsent(num, new ArrayList()); midIndexMap.get(num).add(i); } // 根据中序序列和前序序列还原树结构 TreeNode root buildTree(0, n - 1, 0, n - 1); // 记录新的二叉树的的中序遍历序列 StringJoiner sj new StringJoiner( ); getMidOrder(root, sj); System.out.println(sj); } // 二叉树中序遍历 public static void getMidOrder(TreeNode root, StringJoiner sj) { if (root null) { return; } // 先遍历左子树 TreeNode leftChild root.leftChild; if (leftChild ! null) { getMidOrder(leftChild, sj); } // 再遍历根 sj.add(root.childSum ); // 最后遍历右子树 TreeNode rightChild root.rightChild; if (rightChild ! null) { getMidOrder(rightChild, sj); } } /** * 根据中序遍历序列、前序遍历序列还原树结构 * * param midL 中序遍历子序列的左边界 * param midR 中序遍历子序列的右边界 * param preL 前序遍历子序列的左边界 * param preR 前序遍历子序列的右边界 * return 树结构的根节点 */ public static TreeNode buildTree(int midL, int midR, int preL, int preR) { // 某个节点子树对应一段子序列如果对应子序列范围不存在则子树也不存在 if (preL preR) return null; // 先根据前序遍历序列得到根节点前序序列的首元素就是根节点 int rootNum preOrder[preL]; TreeNode root new TreeNode(rootNum); // 在中序遍历序列中找到对应根值的位置这个位置可能有多个但是只有一个是正确的 for (int idx : midIndexMap.get(rootNum)) { // 如果对应根值位置越界则不是正确的 if (idx midL || idx midR) continue; // 如果中序的左子树和前序的左子树不同则对应根值位置不正确 int leftLen idx - midL; if (notEquals(midL, preL 1, leftLen)) continue; // 如果中序的右子树和前序的右子树不同则对应根值位置不正确 int rightLen midR - idx; if (notEquals(idx 1, preR - rightLen 1, rightLen)) continue; // 找到正确根值位置后开始分治递归处理左子树和右子树 root.leftChild buildTree(midL, idx - 1, preL 1, preL leftLen); root.rightChild buildTree(idx 1, midR, preR - rightLen 1, preR); // 记录该节点左子树右子树的和本题新二叉树节点的值 root.childSum (root.leftChild null ? 0 : (root.leftChild.num root.leftChild.childSum)) (root.rightChild null ? 0 : (root.rightChild.num root.rightChild.childSum)); break; } return root; } /** * 判断两个子数组是否相同元素相同顺序可以不同 * * param midL 子数组1的左边界 * param preL 子数组2的左边界 * param size 子数组的长度 * return 子数组1和子数组2是否相同 */ public static boolean notEquals(int midL, int preL, int size) { int[] arr1 Arrays.stream(Arrays.copyOfRange(midOrder, midL, midL size)).sorted().toArray(); int[] arr2 Arrays.stream(Arrays.copyOfRange(preOrder, preL, preL size)).sorted().toArray(); for (int i 0; i size; i) { if (arr1[i] ! arr2[i]) { return true; } } return false; } }Python算法源码class TreeNode: def __init__(self, num): self.num num self.childSum 0 self.leftChild None self.rightChild None # 输入获取 midOrder list(map(int, input().split())) # 中序遍历序列 preOrder list(map(int, input().split())) # 前序遍历序列 n len(midOrder) # 记录中序遍历序列中序列元素值所在位置本题中可能存在重复元素因此某个序列元素值可能有多个位置 midIndexMap {} for j in range(n): num midOrder[j] midIndexMap.setdefault(num, []) midIndexMap[num].append(j) def notEquals(midL, preL, size): 判断两个子数组是否相同元素相同顺序可以不同 :param midL: 子数组1的左边界 :param preL: 子数组2的左边界 :param size: 子数组的长度 :return: 子数组1和子数组2是否相同 arr1 sorted(midOrder[midL:midLsize]) arr2 sorted(preOrder[preL:preLsize]) for i in range(size): if arr1[i] ! arr2[i]: return True return False def buildTree(midL, midR, preL, preR): 根据中序遍历序列、前序遍历序列还原树结构 :param midL: 中序遍历子序列的左边界 :param midR: 中序遍历子序列的右边界 :param preL: 前序遍历子序列的左边界 :param preR: 前序遍历子序列的右边界 :return: 树结构的根节点 # 某个节点子树对应一段子序列如果对应子序列范围不存在则子树也不存在 if preL preR: return None # 先根据前序遍历序列得到根节点前序序列的首元素就是根节点 rootNum preOrder[preL] root TreeNode(rootNum) # 在中序遍历序列中找到对应根值的位置这个位置可能有多个但是只有一个是正确的 for idx in midIndexMap[rootNum]: # 如果对应根值位置越界则不是正确的 if idx midL or idx midR: continue # 如果中序的左子树和前序的左子树不同则对应根值位置不正确 leftLen idx - midL if notEquals(midL, preL 1, leftLen): continue # 如果中序的右子树和前序的右子树不同则对应根值位置不正确 rightLen midR - idx if notEquals(idx 1, preR - rightLen 1, rightLen): continue # 找到正确根值位置后开始分治递归处理左子树和右子树 root.leftChild buildTree(midL, idx - 1, preL 1, preL leftLen) root.rightChild buildTree(idx 1, midR, preR - rightLen 1, preR) leftChildSum 0 if root.leftChild is None else (root.leftChild.num root.leftChild.childSum) rightChildSUm 0 if root.rightChild is None else (root.rightChild.num root.rightChild.childSum) # 记录该节点左子树右子树的和本题新二叉树节点的值 root.childSum leftChildSum rightChildSUm break return root # 二叉树中序遍历 def getMidOrder(root, res): if root is None: return # 先遍历左子树 leftChild root.leftChild if leftChild is not None: getMidOrder(leftChild, res) # 再遍历根 res.append(root.childSum) # 最后遍历右子树 rightChild root.rightChild if rightChild is not None: getMidOrder(rightChild, res) def getResult(): # 根据中序序列和前序序列还原树结构 root buildTree(0, n - 1, 0, n - 1) # 记录新的二叉树的的中序遍历序列 res [] getMidOrder(root, res) return .join(map(str, res)) # 算法调用 print(getResult())C算法源码#include stdio.h #include stdlib.h #define MAX_SIZE 10000 typedef struct TreeNode { int num; // 当前节点的值 int childSum; // 当前节点的左子树右子树的和 struct TreeNode *leftChild; struct TreeNode *rightChild; } TreeNode; TreeNode *new_TreeNode(int num) { TreeNode *node (TreeNode *) malloc(sizeof(TreeNode)); node-num num; node-childSum 0; node-leftChild NULL; node-rightChild NULL; return node; } // 中序遍历序列 int midOrder[MAX_SIZE]; // 前序遍历序列 int preOrder[MAX_SIZE]; int cmp(const void *a, const void *b) { return *((int *) a) - *((int *) b); } /** * 判断两个子数组是否相同元素相同顺序可以不同 * param midL 子数组1的左边界 * param preL 子数组2的左边界 * param size 子数组的长度 * return 子数组1和子数组2是否相同 */ int notEquals(int midL, int preL, int size) { int arr1[size]; int arr2[size]; for (int i 0; i size; i) { arr1[i] midOrder[midL i]; arr2[i] preOrder[preL i]; } qsort(arr1, size, sizeof(int), cmp); qsort(arr2, size, sizeof(int), cmp); for (int i 0; i size; i) { if (arr1[i] ! arr2[i]) { return 1; } } return 0; } /** * 根据中序遍历序列、前序遍历序列还原树结构 * param midL 中序遍历子序列的左边界 * param midR 中序遍历子序列的右边界 * param preL 前序遍历子序列的左边界 * param preR 前序遍历子序列的右边界 * return 树结构的根节点 */ TreeNode *buildTree(int midL, int midR, int preL, int preR) { // 某个节点子树对应一段子序列如果对应子序列范围不存在则子树也不存在 if (preL preR) return NULL; // 先根据前序遍历序列得到根节点前序序列的首元素就是根节点 int rootNum preOrder[preL]; TreeNode *root new_TreeNode(rootNum); // 在中序遍历序列中找到对应根值的位置这个位置可能有多个但是只有一个是正确的 for (int i midL; i midR; i) { if (midOrder[i] ! rootNum) continue; // 如果中序的左子树和前序的左子树不同则对应根值位置不正确 int leftLen i - midL; if (notEquals(midL, preL 1, leftLen)) continue; // 如果中序的右子树和前序的右子树不同则对应根值位置不正确 int rightLen midR - i; if (notEquals(i 1, preR - rightLen 1, rightLen)) continue; // 找到正确根值位置后开始分治递归处理左子树和右子树 root-leftChild buildTree(midL, i - 1, preL 1, preL leftLen); root-rightChild buildTree(i 1, midR, preR - rightLen 1, preR); // 记录该节点左子树右子树的和本题新二叉树节点的值 root-childSum (root-leftChild NULL ? 0 : (root-leftChild-num root-leftChild-childSum)) (root-rightChild NULL ? 0 : (root-rightChild-num root-rightChild-childSum)); break; } return root; } // 二叉树中序遍历 void getMidOrder(TreeNode* root) { if (root NULL) return; // 先遍历左子树 TreeNode* leftChild root-leftChild; if(leftChild ! NULL) { getMidOrder(leftChild); } // 再遍历根 printf(%d , root-childSum); // 最后遍历右子树 TreeNode* rightChild root-rightChild; if(rightChild ! NULL) { getMidOrder(rightChild); } } int main() { int size 0; while (scanf(%d, midOrder[size])) { if (getchar() ! ) break; } for (int i 0; i size; i) { scanf(%d, preOrder[i]); } // 根据中序序列和前序序列还原树结构 TreeNode *root buildTree(0, size - 1, 0, size - 1); // 打印新的二叉树的的中序遍历序列 getMidOrder(root); return 0; }