树的遍历(已知前序遍历中序遍历求后序遍历,或者已知后序中序求先序)

2023-05-06 16:48:07 浏览数 (1)

假设是1000个结点以内,

输入前序  4 1 3 2 6 5 7

       中序  1 2 3 4 5 6 7 

得到后续  2 3 1 5 7 6 4

已知前序遍历中序遍历求后序遍历:

代码语言:javascript复制
import java.io.BufferedInputStream;
import java.util.Scanner;

class Node {
    int data;
    Node left, right;
}

public class Main {
    public static int[] pre = new int[1001];
    public static int[] in = new int[1001];

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        for (int i = 0; i < n;   i) {
            pre[i] = cin.nextInt();
        }
        for (int i = 0; i < n;   i) {
            in[i] = cin.nextInt();
        }
        cin.close();
        Node head = createTree(pre, 0, in, 0, n);
        postTraverse(head);
    }

    public static void postTraverse(Node node) {
        if (node == null)
            return;
        postTraverse(node.left);
        postTraverse(node.right);
        System.out.print(node.data   " ");
    }
    // 已知先序中序,建树
    // @param pre 先序遍历的数组
    // @param lo 先序遍历的起点下标
    // @param in 中序遍历的数组
    // @param ini 中序遍历的起点下标
    // @param n 这个树的结点个数
    public static Node createTree(int[] pre, int lo, int[] in, int ini, int n) {
        if (n <= 0) {
            return null;
        }
        Node node = new Node();
        node.data = pre[lo];
        int i;
        for (i = 0; i < n;   i) {
            if (pre[lo] == in[ini   i]) // 寻找到该树的根节点就又可以划分左右子树查找了
                break;
        }
        node.left = createTree(pre, lo   1, in, ini, i); // 左区间
        node.right = createTree(pre, lo   i   1, in, ini   i   1, n - i - 1); // 右区间
        // 最后一个参数是这个子树的有多少结点
        return node;
    }
}

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

练习题地址:

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

AC代码:

代码语言:javascript复制
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return reConstructBinaryTree1(pre, 0, in, 0, in.length);
    }

    private TreeNode reConstructBinaryTree1(int[] pre, int lo, int[] in, int ini, int n) {
        if (n <= 0)
            return null;
        TreeNode node = new TreeNode(pre[lo]);
        int i;
        for (i = 0; i < n;   i) {
            if (pre[lo] == in[ini   i])
                break;
        }
        node.left = reConstructBinaryTree1(pre, lo   1, in, ini, i);
        node.right = reConstructBinaryTree1(pre, lo   i   1, in, ini   i   1, n - i - 1);
        return node;
    }
}

0 人点赞