栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

面试题7:重建二叉树【Java实现】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

面试题7:重建二叉树【Java实现】

题目

输入某二叉树的前序遍历和中序遍历结果,请重建该二叉树并输出其后续遍历结果。假设输入的前序遍历和中序遍历结果中都不含重复的数字。树节点定义如下:

class BinaryTreeNode{
    int val;
    BinaryTreeNode left;
    BinaryTreeNode right;
    public BinaryTreeNode(int val) {
		this.val=val;
	}
}
输入:1,2,4,7,3,5,6,8	//前序序列
     4,7,2,1,5,3,8,6  //中序序列
    
输出:7,4,2,5,8,6,3,1	//后序序列    
思路
  • 前序与中序都由三部分【根、左、右】组成,不管哪种遍历方式,他们子树的大小都是一样的
    • 前序:根节点、【左子树】、【右子树】
    • 中序:【左子树】、根节点、【右子树】
  • 前序遍历的第一个一定是根节点,因此我们可以先将其定下来;随后我们要寻找左子树和右子树的分界线,如何寻找呢?中序可以帮助我们
  • 由于前序已经知道了根节点,因此中序只需要遍历数组,将根节点的值与数组元素逐一对比,如果相同的话,就可以定下分界点。根节点左边的元素都是属于左子树的
  • 我们通过这个左子树的大小,就可以确定左子树在前序中的分界点,分别对数组中左子树与右子树的部分进行递归,当前节点的左边就是左子树,当前节点的右边就是右子树
  • 当我们发现左边索引大于右边索引,说明出现越界,即当前的子树是空树,返回null
代码实现
	public static BinaryTreeNode buildTree(int arr1[], int left1, int right1, int arr2[], int left2, int right2) {
		if ( left1 > right1) {
			// 说明此时树中已经没有节点了,是一棵空树
			return null;
		}
		// 前序遍历第一位一定为当前树根节点
		BinaryTreeNode root = new BinaryTreeNode(arr1[left1]);
		int count = 0; // 用于记录左子树大小
		for (int i = left2; i <= right2; i++) {
			if (arr2[i] == root.val) {
				// 说明来到了中序的根节点位置,此时左边为左子树,右边为右子树
				break;
			} else {
				count++;
			}
		}
		// root的左边由左子树构成,根据已知条件传入分割后的前序,中序序列
		root.left = buildTree(arr1, left1 + 1, left1 + count, arr2, left2, left2 + count - 1);
		// root的右边由右子树构成,根据已知条件传入分割后的前序,中序序列
		root.right = buildTree(arr1, left1 + count + 1, right1, arr2, left2 + count+1, right2);
		// 当左右子树都构造完毕后,整棵树也构造完毕
		return root;
	}

	//后序遍历
	public static void postPrint(BinaryTreeNode root) {
		if (root == null) {
			return;
		}
		postPrint(root.left);
		postPrint(root.right);
		System.out.print(root.val + " ");
	}

题目来源于《剑指Offer:名企面试官精讲经典编程题》

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936420.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号