剑指Offer第4题详解（附Java、Python源码）

前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in

class TreeNode {
    int value;
    TreeNode leftTree;
    TreeNode rightTree;
    TreeNode(int x) { value = x; }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                ", leftTree=" + leftTree +
                ", rightTree=" + rightTree +
                '}';
    }
}

import java.util.Arrays;
public class JzOffer4 {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        // 先根据先序遍历建立根结点
        TreeNode root = new TreeNode(pre[0]);

        for (int i=0;i<in.length;i++) {
            if (in[i] == pre[0]) {
                /**
                 * 递归构建左右子树
                 * 注意 copyOfRange 函数，左闭右开
                 */
                root.leftTree = reConstructBinaryTree(Arrays.copyOfRange(pre, 1,i+1 ), Arrays.copyOfRange(in, 0, i));
                root.rightTree = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                break;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        System.out.println(new JzOffer4().reConstructBinaryTree(pre,in).toString());
    }
}

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        prelen = len(pre)
        tinlen = len(tin)
        if prelen == 0 | tinlen == 0 :
            return None
        root = TreeNode(pre[0])
        for i in range(tinlen):
            if tin[i] == pre[0]:
                root.left = self.reConstructBinaryTree(pre[1:i+1], tin[0:i])
                root.right = self.reConstructBinaryTree(pre[i+1:prelen], tin[i+1:tinlen])
                break
        return root