剑指 Offer 07. 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

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

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解法一：递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    record := make(map[int]int)
    for idx, v := range inorder {
        record[v] = idx
    }
    var build func(lp, rp, li, ri int) *TreeNode
    build = func(lp, rp, li, ri int) *TreeNode {
        if lp > rp {
            return nil
        }
        root := &TreeNode{Val: preorder[lp]}
        cnt := record[root.Val] - li
        root.Left = build(lp+1, lp+cnt, li, li+cnt-1)
        root.Right = build(lp+cnt+1, rp, li+cnt+1, ri)
        return root
    }
    return build(0, len(preorder)-1, 0, len(inorder)-1)
}

另一种写法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


/**
 * 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]}
    i := 0
    for i < len(inorder) && inorder[i] != preorder[0] {
        i++
    }
    root.Left = buildTree(preorder[1:i+1], inorder[:i])
    root.Right = buildTree(preorder[i+1:], inorder[i+1:])
    return root
}