剑指offer-重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

输入

前序遍历序列{1,2,4,7,3,5,6,8} 中序遍历序列{4,7,2,1,5,3,8,6}

则重建二叉树并返回。

分析

这道题还是比较简单的，我们知道

前序遍历的顺序为：根左右 中序遍历的顺序为：左根右

递归思想:

1. 我们先根据前序遍历序列的第一个确定根，然后在中序遍历的序列中找到根的位置，根左边的就是其左子树，右边就是其右子树
2. 构建根和左右子树
3. 递归的进行1和2

实现思路

package main

import (
    "fmt"
)

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func printPreOrder(root *TreeNode) {
    if root != nil {
        fmt.Printf("%d ", root.Val)
        printInOrder(root.Left)
        printInOrder(root.Right)
    }
}

func printInOrder(root *TreeNode) {
    if root != nil {
        printInOrder(root.Left)
        fmt.Printf("%d ", root.Val)
        printInOrder(root.Right)
    }
}

func reConstructBinaryTree(pre []int,in []int) *TreeNode {
    if len(pre) != len(in) || len(pre) == 0 {
        return nil
    }

    // find root in preOrder and rootIndex in InOrder
    rootVal := pre[0]
    rootIndex := 0
    for i := 0; i < len(in) ; i++ {
        if in[i] == rootVal {
            rootIndex = i
        }
    }

    inL,inR := in[:rootIndex],in[rootIndex+1:]
    preL, preR := pre[1:rootIndex+1],pre[rootIndex+1:]
    Left := reConstructBinaryTree(preL,inL)
    Right := reConstructBinaryTree(preR,inR)
    return &TreeNode{Val: rootVal, Left: Left, Right: Right}
}

func main() {
    pre := []int{1,2,4,7,3,5,6,8}
    in := []int{4,7,2,1,5,3,6,8}
    fmt.Println("preOder: ", pre)
    fmt.Println("inOrder: ", in)

    // Reconstruct
    fmt.Println("\nReconstruct Binary Tree... \n ",)
    root := reConstructBinaryTree(pre, in)

    // test 
    fmt.Printf("preOder from Tree reconstructed:  ")
    printPreOrder(root)
    fmt.Printf("\n")

    fmt.Printf("inOder from Tree reconstructed:  ")
    printInOrder(root)
    fmt.Printf("\n")
}