通过前、中、后序，任意两种结果来构建二叉树

    前序 和 中序 构建二叉树

    1. /**
    2.  * Definition for a binary tree node.
    3.  * type TreeNode struct {
    4.  *     Val int
    5.  *     Left *TreeNode
    6.  *     Right *TreeNode
    7.  * }
    8.  */
    11. func buildTree(preorder []int, inorder []int) *TreeNode {
    12.     if len(preorder) == 0 {
    13.         return nil
    14.     }
    15.     rootVal := preorder[0]
    16.     i := 0
    17.     // 查找根节点位置
    18.     for ; i < len(inorder); i++ {
    19.         if rootVal == inorder[i] {
    20.             break
    21.         }
    22.     }
    23.     root := &TreeNode{Val: rootVal}
    24.     root.Left = buildTree(preorder[1:i+1], inorder[:i])
    25.     root.Right = buildTree(preorder[i+1:], inorder[i+1:])
    26.     return root
    27. }
    32. func buildTree(preorder []int, inorder []int) *TreeNode {
    33.     if len(preorder) == 0 || len(inorder) == 0 {
    34.             return nil 
    35.     }
    36.     tree := make(map[int]int)
    37.     for k,v :=  range inorder {
    38.         tree[v] = k 
    39.     }
    40.     return build(preorder,inorder,0,len(preorder)-1,0,len(inorder)-1,tree)
    42. }
    44. func build(preorder,inorder []int, p_start,p_end,i_start,i_end int , tree map[int]int) *TreeNode {
    45.     if p_start > p_end {
    46.         return nil 
    47.     }
    48.     root := &TreeNode{Val:preorder[p_start]}
    49.     index,_ := tree[preorder[p_start]]
    50.     preLeftTreeRight := index + p_start - i_start 
    51.     root.Left = build(preorder,inorder,p_start+1,preLeftTreeRight,i_start,index-1,tree)
    52.     root.Right = build(preorder,inorder,preLeftTreeRight+1,p_end,index+1,i_end,tree)
    53.     return root 
    54. }

    中序 和 后序 构建二叉树

    /**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 来看一下一共分几步：

// 第一步：如果数组大小为零的话，说明是空节点了。

// 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

// 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

// 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

// 第五步：切割后序数组，切成后序左数组和后序右数组

// 第六步：递归处理左区间和右区间


func buildTree(inorder []int, postorder []int) *TreeNode {
    if (len(inorder) ==0 || len(postorder)==0) || (len(inorder) != len(postorder)) {
        return nil 
    }
    root := &TreeNode{Val: postorder[len(postorder)-1]} 

    index := 0 
    for k,v := range inorder{
        if v == postorder[len(postorder)-1] {
            index = k 
        }
    }

    left := postorder[:index]  // postorder[:index] inorder[:index] 
    right := postorder[index:len(postorder)-1]  // postorder[index:len(postorder)-1] inorder[index+1:]

    if len(left) > 1 {
        root.Left = buildTree(inorder[:index],postorder[:index])
    } else if len(left) == 1  {
        root.Left = &TreeNode{Val: left[len(left)-1]}
    }

    if len(right) > 1 {
        root.Right = buildTree(inorder[index+1:],postorder[index:len(postorder)-1])
    } else if len(right) == 1  {
        root.Right = &TreeNode{Val: right[len(right)-1]}
    }

    return root 
}


    前序 和 后序 构建二叉树**

    /**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func buildTree(pre []int,post []int ) *TreeNode  {
    N := len(pre)
    if N == 0 {
        return nil
    }
    root := &TreeNode{Val: pre[0]}
    if N == 1 {
        return root
    }
    L := 0
    for i:=0;i<N;i++ {
        if post[i] == pre[1] {
            L = i+1
            break
        }
    }
    root.Left = inorder(pre[1:L+1],post[0:L])
    root.Right = inorder(pre[L+1:N],post[L:N-1])
    return root
}