二叉树的后序遍历

[编程题]二叉树的后序遍历

热度指数：325 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个先序遍历与中序遍历的二叉树，要求求出该二叉树的后序遍历表示形式。对于如下二叉树：

其先序遍历为：GDAFEMHZ

其中序遍历为：ADEFGHMZ

当给定先序遍历与中序遍历时，该二叉树就被唯一的确定下来，这时即可求出二叉树的后序表示为：AEFDHZMG。

给定输入中，二叉树中的字符有且仅有一个，且二叉树中的所有节点互不相同

输入：

两行，第一行为二叉树的先序遍历表示，第二行为二叉树的中序遍历表示

输出：

一行，二叉树的后续遍历表示

示例1

输入

"GDAFEMHZ","ADEFGHMZ"

输出

"AEFDHZMG"

算法知识视频讲解

HRlGhter

"ABDHEICFJKI","DHBEIAJFKCGN"

这个用例有bug，前序序列的最后一行应为G

发表于 2022-04-01 22:02:47 回复(1)

HGHGHG

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param preStr string字符串 
 * @param midStr string字符串 
 * @return string字符串
 */
function binaryTree( preStr ,  midStr ) {
    // write code here
    if(preStr.length==0)return '';
    let rootStr = preStr[0];
    let rootIndex = midStr.indexOf(rootStr);
    let leftMidStr = midStr.slice(0,rootIndex);
    let rightMidStr = midStr.slice(rootIndex+1);
    let leftPreStr = preStr.slice(1,leftMidStr.length+1);
    let rightPreStr = preStr.slice(leftMidStr.length+1);
    return binaryTree(leftPreStr,leftMidStr)+binaryTree(rightPreStr,rightMidStr)+rootStr
}
module.exports = {
    binaryTree : binaryTree
};

发表于 2021-12-08 20:16:29 回复(0)

Java

小小小小🍊

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preStr string字符串 
     * @param midStr string字符串 
     * @return string字符串
     */
    StringBuilder str = new StringBuilder();
    public String binaryTree (String preStr, String midStr) {
        char[] pre = preStr.toCharArray();
        char[] mid = midStr.toCharArray();
        postTree(pre,mid);
        return str.toString();
    }
    public void postTree(char[] preStr , char[] midStr){
        if(preStr.length == 1) {
            str.append(preStr[0]);
            return;
        }
        int n = findNode(preStr[0],midStr);
        if(n!=1){
            char[] preleft = Arrays.copyOfRange(preStr,1,n);
            char[] midleft = Arrays.copyOfRange(midStr,0,n-1);
            postTree(preleft,midleft);
        }
        if(n != preStr.length){
            char[] preright = Arrays.copyOfRange(preStr,n,preStr.length);
            char[] midright = Arrays.copyOfRange(midStr,n,midStr.length);
            postTree(preright,midright);
        }
        str.append(preStr[0]);
        
    }
    
    public int findNode(char ch,char[] midStr){
        int n = 0;
        for(int i = 0 ; i<midStr.length ; ++i){
            if(midStr[i] == ch){
                n = i;
            }
        }
        return n+1;
    }
}

发表于 2021-08-17 15:33:10 回复(0)