核心代码编程- 输出二叉树后序遍历结果-200分

题目描述给定二叉树前序遍历和中序遍历的字符串以及需要删除的节点要求先解析这两个字符串获取对应二叉树再做删除指定节点操作然后输出该二叉树的后序遍历结果。删除节点规则1、指定节点是根节点则不做删除操作2、指定节点是叶子节点则直接删除3、指定节点是内部节点(1如果是左子节点则把该节点的左子树挂接到它的父节点然后删除该节点以及它的右子树(2如果是右子节点则把该节点的右子树挂接到它的父节点然后删除该节点以及它的左子树。输入string preorderStr /前序遍历字符串string inorderStr /中序遍历字符串char beDeletedNode // 待删除的节点输出string outputStr /返回或者 后序遍历的字符串注1、给定的preorderStr和inorderStr是由大写字母组成的字符串长度为2~26每个字母表示一个节点值且节点值唯一2、给定的beDeletedLeafNode是一个大写字母如果输入的不是大写字母、或者找不到对应节点、或者找到的节点是根节点都不做删除操作3、如果做了删除操作则输出删除叶子节点后的二叉树后序遍历结果否则直接输出二叉树后序遍历结果4、preorderStr和inorderStr符合如下场景则输出空串例如(1字符串中存在非大写字母(2长度超出范围(3节点值不唯一(4两个字符串长度不一致(5两个字符串元素不相同(6无法解析出对应二叉树。说明1、程序运行内存要小于256MB;2、程序运行耗时不能超过1秒。补充说明示例1输入23a,ABC,A 输出说明输入存在非法字符串示例2输入 ADE,DAE,E输出DA说明示例3输入AABCD,BAACD,A输出说明出现重复节点值示例4输入ABC,BAC,A输出BCA说明找到的节点A是根节点示例5输入ABCDE,BAHDE,E输出说明输入的两个遍历结果元素不相同以下是我用Python实现的代码严格遵循题目要求def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) root_index inorder.find(root_val) if root_index -1: return None root.left build_tree(preorder[1:1root_index], inorder[:root_index]) root.right build_tree(preorder[1root_index:], inorder[root_index1:]) return root def find_node(root, target, parentNone): if not root: return None, None if root.val target: return root, parent left_node, left_parent find_node(root.left, target, root) if left_node: return left_node, left_parent return find_node(root.right, target, root) def postorder_traversal(root): if not root: return left postorder_traversal(root.left) right postorder_traversal(root.right) return left right root.val def delete_node(root, target): target_node, parent find_node(root, target) if not target_node or not parent: # 根节点或未找到 return False # 叶子节点 if not target_node.left and not target_node.right: if parent.left target_node: parent.left None else: parent.right None return True # 内部节点处理 if parent.left target_node: # 左子节点 parent.left target_node.left else: # 右子节点 parent.right target_node.right return True def main(preorderStr, inorderStr, beDeletedNode): # 验证输入合法性 if (len(preorderStr) 2 or len(preorderStr) 26 or len(inorderStr) 2 or len(inorderStr) 26 or len(preorderStr) ! len(inorderStr) or not beDeletedNode.isupper() or set(preorderStr) ! set(inorderStr) or len(set(preorderStr)) ! len(preorderStr)): return # 构建二叉树 root build_tree(preorderStr, inorderStr) if not root: return # 尝试删除节点 if beDeletedNode ! root.val: deleted delete_node(root, beDeletedNode) # 返回后序遍历结果 return postorder_traversal(root) class TreeNode: def __init__(self, val): self.val val self.left None self.right None以下是Java实现import java.util.*; class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char x) { val x; } } public class Solution { public static String main(String preorderStr, String inorderStr, char beDeletedNode) { if (preorderStr null || inorderStr null || preorderStr.length() 2 || preorderStr.length() 26 || inorderStr.length() 2 || inorderStr.length() 26 || preorderStr.length() ! inorderStr.length() || !Character.isUpperCase(beDeletedNode)) { return ; } SetCharacter set new HashSet(); for (char c : preorderStr.toCharArray()) { if (!Character.isUpperCase(c)) return ; set.add(c); } for (char c : inorderStr.toCharArray()) { if (!Character.isUpperCase(c)) return ; if (!set.contains(c)) return ; } if (set.size() ! preorderStr.length()) return ; TreeNode root buildTree(preorderStr, inorderStr); if (root null) return ; if (root.val ! beDeletedNode) { deleteNode(root, beDeletedNode); } return postorderTraversal(root); } private static TreeNode buildTree(String preorder, String inorder) { if (preorder.isEmpty() || inorder.isEmpty()) return null; char rootVal preorder.charAt(0); TreeNode root new TreeNode(rootVal); int rootIndex inorder.indexOf(rootVal); if (rootIndex -1) return null; root.left buildTree(preorder.substring(1, 1 rootIndex), inorder.substring(0, rootIndex)); root.right buildTree(preorder.substring(1 rootIndex), inorder.substring(rootIndex 1)); return root; } private static void deleteNode(TreeNode root, char target) { TreeNode[] result findNode(root, target, null); if (result[0] null || result[1] null) return; // 根节点或未找到 TreeNode targetNode result[0]; TreeNode parent result[1]; if (targetNode.left null targetNode.right null) { if (parent.left targetNode) parent.left null; else parent.right null; return; } if (parent.left targetNode) { parent.left targetNode.left; } else { parent.right targetNode.right; } } private static TreeNode[] findNode(TreeNode node, char target, TreeNode parent) { if (node null) return new TreeNode[]{null, null}; if (node.val target) return new TreeNode[]{node, parent}; TreeNode[] left findNode(node.left, target, node); if (left[0] ! null) return left; return findNode(node.right, target, node); } private static String postorderTraversal(TreeNode root) { if (root null) return ; return postorderTraversal(root.left) postorderTraversal(root.right) root.val; } }以下是C实现#include iostream #include string #include unordered_set using namespace std; struct TreeNode { char val; TreeNode *left; TreeNode *right; TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} }; TreeNode* buildTree(string preorder, string inorder) { if (preorder.empty() || inorder.empty()) return nullptr; char rootVal preorder[0]; TreeNode* root new TreeNode(rootVal); size_t rootIndex inorder.find(rootVal); if (rootIndex string::npos) return nullptr; root-left buildTree(preorder.substr(1, rootIndex), inorder.substr(0, rootIndex)); root-right buildTree(preorder.substr(1 rootIndex), inorder.substr(rootIndex 1)); return root; } pairTreeNode*, TreeNode* findNode(TreeNode* node, char target, TreeNode* parent) { if (!node) return {nullptr, nullptr}; if (node-val target) return {node, parent}; auto left findNode(node-left, target, node); if (left.first) return left; return findNode(node-right, target, node); } void deleteNode(TreeNode* root, char target) { auto result findNode(root, target, nullptr); if (!result.first || !result.second) return; // Root or not found TreeNode* targetNode result.first; TreeNode* parent result.second; if (!targetNode-left !targetNode-right) { if (parent-left targetNode) parent-left nullptr; else parent-right nullptr; return; } if (parent-left targetNode) { parent-left targetNode-left; } else { parent-right targetNode-right; } } string postorderTraversal(TreeNode* root) { if (!root) return ; return postorderTraversal(root-left) postorderTraversal(root-right) root-val; } string main(string preorderStr, string inorderStr, char beDeletedNode) { if (preorderStr.length() 2 || preorderStr.length() 26 || inorderStr.length() 2 || inorderStr.length() 26 || preorderStr.length() ! inorderStr.length() || !isupper(beDeletedNode)) { return ; } unordered_setchar set; for (char c : preorderStr) { if (!isupper(c)) return ; set.insert(c); } for (char c : inorderStr) { if (!isupper(c)) return ; if (set.find(c) set.end()) return ; } if (set.size() ! preorderStr.length()) return ; TreeNode* root buildTree(preorderStr, inorderStr); if (!root) return ; if (root-val ! beDeletedNode) { deleteNode(root, beDeletedNode); } return postorderTraversal(root); }以下是JavaScript实现class TreeNode { constructor(val) { this.val val; this.left null; this.right null; } } function buildTree(preorder, inorder) { if (!preorder.length || !inorder.length) return null; const rootVal preorder[0]; const root new TreeNode(rootVal); const rootIndex inorder.indexOf(rootVal); if (rootIndex -1) return null; root.left buildTree(preorder.slice(1, 1 rootIndex), inorder.slice(0, rootIndex)); root.right buildTree(preorder.slice(1 rootIndex), inorder.slice(rootIndex 1)); return root; } function findNode(node, target, parent) { if (!node) return [null, null]; if (node.val target) return [node, parent]; const left findNode(node.left, target, node); if (left[0]) return left; return findNode(node.right, target, node); } function deleteNode(root, target) { const [targetNode, parent] findNode(root, target, null); if (!targetNode || !parent) return; // Root or not found if (!targetNode.left !targetNode.right) { if (parent.left targetNode) parent.left null; else parent.right null; return; } if (parent.left targetNode) { parent.left targetNode.left; } else { parent.right targetNode.right; } } function postorderTraversal(root) { if (!root) return ; return postorderTraversal(root.left) postorderTraversal(root.right) root.val; } function main(preorderStr, inorderStr, beDeletedNode) { if (preorderStr.length 2 || preorderStr.length 26 || inorderStr.length 2 || inorderStr.length 26 || preorderStr.length ! inorderStr.length || !/[A-Z]/.test(beDeletedNode)) { return ; } const set new Set(); for (let c of preorderStr) { if (!/[A-Z]/.test(c)) return ; set.add(c); } for (let c of inorderStr) { if (!/[A-Z]/.test(c)) return ; if (!set.has(c)) return ; } if (set.size ! preorderStr.length) return ; const root buildTree(preorderStr, inorderStr); if (!root) return ; if (root.val ! beDeletedNode) { deleteNode(root, beDeletedNode); } return postorderTraversal(root); }以下是Go实现package main import ( strings ) type TreeNode struct { Val byte Left *TreeNode Right *TreeNode } func buildTree(preorder, inorder string) *TreeNode { if len(preorder) 0 || len(inorder) 0 { return nil } rootVal : preorder[0] root : TreeNode{Val: rootVal} rootIndex : strings.IndexByte(inorder, rootVal) if rootIndex -1 { return nil } root.Left buildTree(preorder[1:1rootIndex], inorder[:rootIndex]) root.Right buildTree(preorder[1rootIndex:], inorder[rootIndex1:]) return root } func findNode(node *TreeNode, target byte, parent *TreeNode) (*TreeNode, *TreeNode) { if node nil { return nil, nil } if node.Val target { return node, parent } if leftNode, leftParent : findNode(node.Left, target, node); leftNode ! nil { return leftNode, leftParent } return findNode(node.Right, target, node) } func deleteNode(root *TreeNode, target byte) { targetNode, parent : findNode(root, target, nil) if targetNode nil || parent nil { return } if targetNode.Left nil targetNode.Right nil { if parent.Left targetNode { parent.Left nil } else { parent.Right nil } return } if parent.Left targetNode { parent.Left targetNode.Left } else { parent.Right targetNode.Right } } func postorderTraversal(root *TreeNode) string { if root nil { return } return postorderTraversal(root.Left) postorderTraversal(root.Right) string(root.Val) } func main(preorderStr, inorderStr string, beDeletedNode byte) string { if len(preorderStr) 2 || len(preorderStr) 26 || len(inorderStr) 2 || len(inorderStr) 26 || len(preorderStr) ! len(inorderStr) || beDeletedNode A || beDeletedNode Z { return } set : make(map[byte]bool) for i : 0; i len(preorderStr); i { c : preorderStr[i] if c A || c Z { return } set[c] true } for i : 0; i len(inorderStr); i { c : inorderStr[i] if c A || c Z { return } if !set[c] { return } } if len(set) ! len(preorderStr) { return } root : buildTree(preorderStr, inorderStr) if root nil { return } if root.Val ! beDeletedNode { deleteNode(root, beDeletedNode) } return postorderTraversal(root) }