依据前序,中序结构二叉树1. 题目形容输出某二叉树的前序遍历和中序遍历的后果,请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。
2. 示例例如,给出
前序遍历 preorder = [3,9,20,15,7] 根, 左, 右
中序遍历 inorder = [9,3,15,20,7] 左, 根, 右
返回如下的二叉树:
3. 解题思路思路:前序的第一个元素是根结点的值,在中序中找到该值,中序中该值的右边的元素是根结点的左子树,左边是右子树,而后递归的解决右边和左边
具体来说,前序遍历的第一个值肯定为根节点,对应于中序遍历两头的一个点。在中序遍历序列中,这个点左侧的均为根的左子树,这个点右侧的均为根的右子树。这时能够利用递归,别离取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树持续上一个过程,取前序遍历[i+1:]和中序遍历[i+1]对应于右子树持续上一个过程,最终得以重建二叉树。
Python解决会比较简单一些
4. Java实现/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.Arrays; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] tin) { if (pre.length == 0 || tin.length == 0){ return null; } TreeNode root = new TreeNode(pre[0]); // 找到 第一个元素在 tin 中的地位 int i = getIndex(tin, pre[0]); root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(tin, 0, i)); root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(tin, i+1, tin.length)); return root; } private int getIndex(int[] array, int value){ int index = 0; for (int i = 0; i < array.length; i++){ if (array[i] == value){ index = i; break; } } return index; }}5. Python实现'''输出某二叉树的前序遍历和中序遍历的后果,请重建出该二叉树。假如输出的前序遍历和中序遍历的后果中都不含反复的数字。例如输出前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。''' class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: # 返回结构的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if not pre or not tin: #只有一个数组为空,则退出函数 return if set(pre) != set(tin):#如果数组中有反复元素 return root = TreeNode(pre[0]) i = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1: i+1], tin[: i]) root.right = self.reConstructBinaryTree(pre[i+1: ], tin[i+1: ]) return root pre = [1, 2, 3, 5, 6, 4]tin = [5, 3, 6, 2, 4, 1]test = Solution()newTree = test.reConstructBinaryTree(pre, tin)print(newTree)#中序遍历def inorder(newTree): if newTree: inorder(newTree.left) print(newTree.val) inorder(newTree.right)inorder(newTree) ...