输出二叉树后序遍历结果

更多语言题解可查看：华为OD机试新系统真题 - 输出二叉树后序遍历结果(C/C++/Py/Java/Js/Go)题解

题目内容

给定二叉树前序遍历和中序遍历的字符串，以及需要删除的节点，要求先解析这两个字符串获取对应二叉树，再做删除指定节点操作，然后输出该二叉树的后序遍历结果。删除节点规则：

1. 指定节点是根节点，则不做删除操作；
2. 指定节点是叶子节点，则直接删除；
3. 指定节点是内部节点：
   • 如果是左子节点，则把该节点的左子树挂接到它的父节点，然后删除该节点以及它的右子树；
   • 如果是右子节点，则把该节点的右子树挂接到它的父节点，然后删除该节点以及它的左子树。

输入描述

$string$ $preorderStr$ // 前序遍历字符串
$string$ $inorderStr$ // 中序遍历字符串
$char$ $beDeletedNode$ // 待删除的节点

输出描述

$string$ $outputStr$ // 返回 “” 或者 后序遍历的字符串

补充说明：

1. 给定的$preorderStr$ 和 $inorderStr$ 是由大写字母组成的字符串，长度为$2$ ~ $26$，每个字母表示一个节点值，且节点值唯一；
2. 给定的 $beDeletedLeafNode$ 是一个大写字母，如果输入的不是大写字母、或者找不到对应节点、或者找到的节点是根节点，都不做删除操作；
3. 如果做了删除操作，则输出删除叶子节点后的二叉树后序遍历结果，否则直接输出二叉树后序遍历结
4. $preorderStr$ 和 $inorderStr$ 符合如下场景则输出空串""，例如：
   • 字符串中存在非大写字母；
   • 长度超出范围；
   • 节点值不唯一；
   • 两个字符串长度不一致；
   • 两个字符串元素不相同；
   • 无法解析出对应二叉树。

样例1

输入

23a
ABC
A

输出

说明

输入存在非法字符串

样例2

输入

ADE
DAE
E

输出

DA

样例3

输入

AABCD
BAACD
A

输出

说明

出现重复节点值

样例4

输入

ABC
BAC
A

输出

BCA

说明

找到的节点 $A$ 是根节点

样例5

输入

ABCDE
BAHDE
E

输出

""

说明

输入的两个遍历结果元素不相同

题解

思路

思路：二叉树

1. 首先判断以下几个非法情况，存在非法情况直接返回空字符串:
   • 前序遍历和后序遍历长度是否不一致
   • 前序遍历或后序遍历长度是否超过限制
   • 判断前序遍历和后序遍历是否包含重复字符或者非大写字母以及元素是否不同。
2. 利用前序遍历和后序遍历结果还原二叉树，前序遍历的顺序为父节点->左子->右子，中序遍历顺序为左子->父节点->右子,简单说说还原逻辑以ABDECFH和DBEAFCH为例
   1. 根据前序遍历规律,可以得出第一个值是父节点的值A。
   2. 在中序遍历种找到对应的父节点的值所处位置j =3， 根据中序遍历规律此时可知，DBE为左子树中序遍历结果，FCH为右子树中序遍历结果。
   3. 根据中序遍历得知左右子树长度之后，同时也可知道左子树前序遍历结果为BDE，右子树前序遍历结果为CFH
   4. 按照上述1，2，3的规律使用递归即可还原出二叉树。
3. 2为正确遍历结果还原结果的方法，无法构建二叉树可在二叉树递归还原进行判断，例如前序和中序节点不一致，无法在中序遍历结果中找到父节点。发生上面情况时标记为非法并直接终止构建即可。
4. 删除节点比较简单，题目要求不会删除根节点，如果根节点等于要删除节点不进行处理。接下来进行递归删除，处理逻辑如下，当前节点为current
   • 如果current->left != null, 并且root->left->value == beDeletedNode,将左子的左子树挂载到当前节点的左子树位置即可。
   • 如果current->root != null, 并且root->right->value == beDeletedNode,将右子节点的右子树挂载到当前节点的右子树位置即可。
5. 接下来递归生成当前二叉树的后序遍历结果即可。这部分很简单，可参照下面代码。

往期真题通过中序、后序遍历还原二叉树，感兴趣的看看:华为OD机试真题-二叉树的广度优先遍历

code

import java.io.*;
import java.util.*;

public class Main {

    static class Node {
        Node left;
        Node right;
        char value;

        Node() {}

        Node(char value) {
            this.value = value;
        }
    }

    static boolean valid = true;

    // 通过前序和中序还原二叉树
    static Node generateNode(String preorder, String inOrder) {
        if (preorder.isEmpty()) {
            return null;
        }
        if (preorder.length() != inOrder.length()) {
            valid = false;
            return null;
        }

        int n = preorder.length();
        Node root = new Node(preorder.charAt(0));

        // 确定左子树的长度
        int j = 0;
        for (; j < n; j++) {
            if (preorder.charAt(0) == inOrder.charAt(j)) {
                break;
            }
        }

        // 指定节点找不到
        if (j == n) {
            valid = false;
            return null;
        }

        // 确定左右子树中序遍历结果
        String inOrderLeft = inOrder.substring(0, j);
        String inOrderRight = inOrder.substring(j + 1);

        // 确定左右子树前序遍历结果
        String preorderLeft = preorder.substring(1, j+1);
        String preorderRight = preorder.substring(j + 1);

        if (!inOrderLeft.isEmpty()) {
            root.left = generateNode(preorderLeft, inOrderLeft);
        }
        if (!inOrderRight.isEmpty()) {
            root.right = generateNode(preorderRight, inOrderRight);
        }
        return root;
    }

    // 递归获取后序遍历结果
    static String dfs(Node root) {
        if (root == null) {
            return "";
        }
        String res = "";
        res += dfs(root.left);
        res += dfs(root.right);
        res += root.value;
        return res;
    }

    // 统计每个大写字母数量并判断是否包含除大写字母之外其它字符
    static boolean countChar(int[] count, String str) {
        for (char c : str.toCharArray()) {
            if (c <= 'Z' && c >= 'A') {
                count[c - 'A']++;
            } else {
                return false;
            }
        }
        return true;
    }

    // 移除指定节点
    static void removeNode(Node root, char c) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            // 移除
            if (root.left.value == c) {
                root.left = root.left.left;
                return;
            }
            // 递归向下
            removeNode(root.left, c);
        }

        if (root.right != null) {
            // 移除
            if (root.right.value == c) {
                root.right = root.right.right;
                return;
            }
            // 递归向下
            removeNode(root.right, c);
        }
    }

    static String deleteTreeNode(String preorderStr, String inorderStr, char beDeletedNode) {

        // 判断非法情况

        // 长度不一致
        if (preorderStr.length() != inorderStr.length()) {
            return "";
        }
        // 长度超过限制
        if (preorderStr.length() > 26 || preorderStr.length() < 2) {
            return "";
        }

        int[] countA = new int[26], countB = new int[26];

        boolean flag = countChar(countA, preorderStr);
        // 包含非大写字符
        if (!flag) {
            return "";
        }

        flag = countChar(countB, inorderStr);
        if (!flag) {
            return "";
        }

        // 判断是否存在重复元素，以及两个字符串元素是否相同
        for (int i = 0; i < 26; i++) {
            if (countA[i] != countB[i]) {
                return "";
            }
            if (countA[i] > 1) {
                return "";
            }
        }

        // 构造出对应二叉树
        Node root = generateNode(preorderStr, inorderStr);

        // 无法构造出对应二叉树
        if (!valid) {
            return "";
        }

        // 未root情况才需要进行移除
        if (!(root.value == beDeletedNode)) {
            removeNode(root, beDeletedNode);
        }

        // 获取对应后序遍历结果
        String res = dfs(root);
        return res;
    }

// 作者 csdn无限码力
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String preorderStr = br.readLine();
        String inorderStr = br.readLine();
        char beDeletedNode = br.readLine().charAt(0);

        System.out.print(deleteTreeNode(preorderStr, inorderStr, beDeletedNode));
    }
}