LeetCode 105. 从前序与中序遍历序列构造二叉树Golang版

1. 问题描述

2. 思路

经典的二叉建树题目
给定前序遍历和中序遍历可以建立唯一二叉树，给定后序遍历和中序遍历可以建立二叉树。

1. 根据preorder找到根节点，即preorder[0]
2. 在inorder中找到左子树和右子树 即inorder[:i]以及inorder[i+1:]
3. 在preorder中找到左子树和右子树，preorder[1:i+1]以及inorder[i+1:]
   递归构建左子树和右子树

3. 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }

    root := &TreeNode {
        Val : preorder[0],
        Left: nil,
        Right: nil,
    }

    i := 0;
    for ;i < len(inorder); i++ {
        if root.Val == inorder[i] {
            break
        }
    }

    root.Left = buildTree(preorder[1:i+1], inorder[:i])
    root.Right = buildTree(preorder[i+1:], inorder[i+1:])
    return root
}