of007.md

description
剑指 Offer 07. 重建二叉树

OF7.重建二叉树

题目描述

题目地址

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

     3
    / \
   9  20
   /   \
  15    7

题解

思路1 ： ...

递归遍历

算法流程：

1. 复杂度分析：
2. 时间复杂度$$O(N)$$：
3. 空间复杂度$$O(N)$$：

代码

{% tabs %} {% tab title="Go" %}

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

//	递归求解
func buildTree(pre []int, in []int) *TreeNode {
	if len(pre) == 0 || len(in) == 0 {
		return nil
	}
	mid := search(in, pre[0])
	return &TreeNode{
		Val:   pre[0],
		Left:  buildTree(pre[1:mid+1], in[:mid+1]),
		Right: buildTree(pre[mid+1:], in[mid+1:]),
	}
}
func search(nodes []int, val int) int {
	for p, v := range nodes {
		if v == val {
			return p
		}
	}
	return -1
}

{% endtab %}

{% tab title="Python" %}

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        def helper(in_left = 0, in_right = len(inorder)):
            nonlocal pre_idx
            # if there is no elements to construct subtrees
            if in_left == in_right:
                return None
            
            # pick up pre_idx element as a root
            root_val = preorder[pre_idx]
            root = TreeNode(root_val)

            # root splits inorder list
            # into left and right subtrees
            index = idx_map[root_val]

            # recursion 
            pre_idx += 1
            # build left subtree
            root.left = helper(in_left, index)
            # build right subtree
            root.right = helper(index + 1, in_right)
            return root
        
        # start from first preorder element
        pre_idx = 0
        # build a hashmap value -> its index
        idx_map = {val:idx for idx, val in enumerate(inorder)} 
        return helper()

{% endtab %} {% endtabs %}

总结

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：awesome-golang-algorithm