前序與中序周遊序列構造二叉樹

leetcode 105. 從前序與中序周遊序列構造二叉樹

• 前序 根-左子樹-右子樹
• 中序 左-根-右
• 前序序列中，第一個是根，然後是所有左子樹節點，再是右子樹節點
• 中序序列中，左子樹都在根左邊，右子樹都在根右邊。
• 根據中序序列的左子樹長度，得到右子樹根節點在前序序列的位置

func buildTree(preorder []int, inorder []int) *TreeNode {
	n := len(preorder)
	if n == 0 {
		return nil
	}
	// 找到根在中序的位置
	var i int
	for i = 0; i < n; i++ {
		if inorder[i] == preorder[0] {
			break
		}
	}
	root := &TreeNode{
		Val:   preorder[0],
		Left:  buildTree(preorder[1:1+i], inorder[:i]),		
		Right: buildTree(preorder[i+1:], inorder[i+1:]),
	}
	return root
}