根据先序遍历和中序遍历生成后序遍历

作者:Grey

原文地址: 根据先序遍历和中序遍历生成后序遍历

问题描述

牛客:通过先序和中序数组生成后序数组

思路

假设有一棵二叉树

《根据先序遍历和中序遍历生成后序遍历》

先序遍历的结果是

《根据先序遍历和中序遍历生成后序遍历》

中序遍历的结果是

《根据先序遍历和中序遍历生成后序遍历》

由于先序遍历大的调度逻辑是,先头,再左,再右

后序遍历的调度逻辑是:先左,再右,再头。

所以:后序遍历的最后一个节点,一定是先序遍历的头节点

定义递归函数

// 先序遍历数组pre的[l1...r1]区间
// 中序遍历数组in的[l2...r2]区间
// 生成后序遍历数组pos的[l3...r3]区间
void func(int[] pre, int l1, int r1, int[] in, int l2, int r2, int[] pos, int l3, r3)

依据以上推断,可以得到如下结论

// 后序遍历的最后一个节点,一定是先序遍历的头节点
pos[r3] = pre[l1];

然后,在中序数组中,我们可以定位到这个头节点的位置,即下图中标黄的位置,假设这个位置是index

《根据先序遍历和中序遍历生成后序遍历》

这个index将中序数组分成了左右两个部分,由于中序遍历的调度过程是:先左,再头,再右,所以在中序遍历中[l2......index]区间内,是以index位置为头的左树中序遍历结果,[l2......index]区间内元素个数假设为b,那么在先序遍历中,从头往后数b个元素,即:[l1......l1+b]构成了以index位置为头的左树的先序遍历结果。

	public static void func(int[] pre, int l1, int r1, int[] in, int l2, int r2, int[] pos, int l3, int r3) {
		if (l1 > r1) {
			// 避免了无效情况
			return;
		}
		if (l1 == r1) {
			// 只有一个数的时候
			pos[l3] = pre[l1];
		} else {
			// 不止一个数的时候
			pos[r3] = pre[l1];
			// index表示某个头在中序数组中的位置
			int index;
			for (index = l2; index <= r2; index++) {
				if (in[index] == pre[l1]) {
					break;
				}
			}
			int b = index - l2;
            // 构造左树
			func(pre, l1 + 1, l1 + b, in, l2, index - 1, pos, l3, l3 + b - 1);
		   // 构造右树
            func(pre, l1 + b + 1, r1, in, index + 1, r2, pos, l3 + b, r3 - 1);
		}
	}

优化

在递归函数func中,有一个遍历的行为,

			for (index = l2; index <= r2; index++) {
				if (in[index] == pre[l1]) {
					break;
				}
			}

如果每次递归都要遍历一下,那么效率会降低,所以可以在一开始就设置一个map,存一下中序遍历中每个值所在的位置信息,这样就不需要通过遍历来找位置了,方法如下:

		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			inOrder[i] = in.nextInt();
			map.put(inOrder[i], i);
		}

这样预处理以后,每次index的位置不需要遍历得到,只需要

			int index = map.get(pre[l1]);

即可,完整代码见

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] preOrder = new int[n];
		int[] inOrder = new int[n];
		for (int i = 0; i < n; i++) {
			preOrder[i] = in.nextInt();
		}
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			inOrder[i] = in.nextInt();
			map.put(inOrder[i], i);
		}
		int[] posOrder = new int[n];
		func(preOrder, 0, n - 1, inOrder, 0, n - 1, posOrder, 0, n - 1, map); 
		for (int i = 0; i < n; i++) {
			System.out.print(posOrder[i] + " ");
		}
		in.close();
	}


	public static void func(int[] pre, int l1, int r1, int[] in, int l2, int r2, int[] pos, int l3, int r3,
			Map<Integer, Integer> map) {
		if (l1 > r1) {
			// 避免了无效情况
			return;
		}
		if (l1 == r1) {
			// 只有一个数的时候
			pos[l3] = pre[l1];
		} else {
			// 不止一个数的时候
			pos[r3] = pre[l1];
			// index表示某个头在中序数组中的位置
			int index = map.get(pre[l1]);
			int b = index - l2;
			func(pre, l1 + 1, l1 + b, in, l2, index - 1, pos, l3, l3 + b - 1, map);
			func(pre, l1 + b + 1, r1, in, index + 1, r2, pos, l3 + b, r3 - 1, map);
		}
	}

}

更多

算法和数据结构笔记

    原文作者:Grey Zeng
    原文地址: https://www.cnblogs.com/greyzeng/p/16406847.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞