刷题使我快乐，满脸开心.jpg

  • 来源：力扣（LeetCode）
  • 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
  • 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

思路

还是头一次思考构建树的问题，整理了下思路，发现其实考查的就是对于两种遍历方式的理解。

前序遍历：对于每一个节点及其左右子节点的组合来说，总是以根->左->右的顺序遍历节点
中序遍历：对于每一个节点及其左右子节点的组合来说，总是以左->根->右的顺序遍历节点

基于这个特性，我们再来看两个遍历方式的数组，就可以用这个思路来分解问题

  • 对于一棵树来说，前序遍历的第一个元素即是树的根节点
  • 对于中序遍历数组中，根节点左边的元素都是其左子树的元素；根节点右边的元素都是其右子树的元素

有了这个概念，我们就可以分解问题了：

  • 一层层往下拆解子树，这就是递归方法的递归条件
  • 直到没有节点、仅剩一个节点，此时就可以直接返回了，这就是递归方法的退出条件

至此，递归方法的要素就凑齐了，这里我的代码，不如官方解法简洁，但是感觉能更加直接的看出拆解左右子树的过程

另外放了官方递归的代码，方便看下更简洁的写法~

老样子，细节在代码注释了，上代码~

代码

个人递归解法

func buildTree(preorder []int, inorder []int) *TreeNode {
    // 四个参数均为数组下标
	var getTree func(inStart, inEnd, preStart, preEnd int) *TreeNode
	getTree = func(inStart, inEnd, preStart, preEnd int) *TreeNode {
		if preStart > preEnd {
			return nil
		}

		root := &TreeNode{Val: preorder[preStart]}
        // 可有可无，不写就会多进一层递归，然后return nil返回
		if preStart == preEnd {
			return root
		}

		i := inStart
		for ; i <= inEnd; i++ {
			if preorder[preStart] == inorder[i] {
				break
			}
		}
		// 四个参数均为数组下标
        // 前序遍历中，左子树的节点们就是以根节点之后第一个元素开始
		leftPreStart := preStart + 1
		// 根据中序遍历数组，可以知道根节点位置和起始位置之间的差值就是左子树长度
		leftLen := i - inStart
		// 前序遍历中，右子树的节点起点就是以左子树起点坐标加上左子树长度
		rightPreStart := leftPreStart + leftLen
		root.Left = getTree(inStart, i-1, leftPreStart, rightPreStart-1)
		root.Right = getTree(i+1, inEnd, rightPreStart, preEnd)
		return root
	}
	return getTree(0, len(inorder)-1, 0, len(preorder)-1)
}

官方递归解法

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