关于数据结构:剑指offer4根据前序中序构造二叉树JavaPython

依据前序，中序结构二叉树

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 = None
class 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)