LeetCode_105 . 从前序和中序遍历构造二叉树

问题描述：

        给定两个整数数组preorder，inorder其中preorder是二叉树的前inorder序遍历， 是同一棵树的中序遍历，构造并返回二叉树。

示例：

思路：

        先序遍历数组中的第一个元素为根节点，在中序中找到根节点位置，数组左边的数字为根节点的左孩子中的数字，数组右边的数字为根节点右孩子中的数字，依次遍历。

代码：

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public static TreeNode buildTree1(int[] pre, int[] in) {if (pre == null || in == null || pre.length != in.length) {return null;}return f(pre, 0, pre.length - 1, in, 0, in.length - 1);}// 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]// 请建出整棵树返回头节点public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2) {if (L1 > R1) {return null;}TreeNode head = new TreeNode(pre[L1]);if (L1 == R1) {return head;}int find = L2;while (in[find] != pre[L1]) {find++;}head.left = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);head.right = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);return head;}public static TreeNode buildTree2(int[] pre, int[] in) {if (pre == null || in == null || pre.length != in.length) {return null;}HashMap valueIndexMap = new HashMap<>();for (int i = 0; i < in.length; i++) {valueIndexMap.put(in[i], i);}return g(pre, 0, pre.length - 1, in, 0, in.length - 1, valueIndexMap);}// 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]// 请建出整棵树返回头节点public static TreeNode g(int[] pre, int L1, int R1, int[] in, int L2, int R2,HashMap valueIndexMap) {if (L1 > R1) {return null;}TreeNode head = new TreeNode(pre[L1]);if (L1 == R1) {return head;}int find = valueIndexMap.get(pre[L1]);head.left = g(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, valueIndexMap);head.right = g(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, valueIndexMap);return head;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！