• Difficulty: Medium

• Related Topics: Array, Tree, Depth-first Search

• Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Description

Given preorder and inorder traversal of a tree, construct the binary tree.Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

给定二叉树的前序和中序遍历，构建这棵二叉树。这题其实不难，前序遍历的第一个就是 root，然后用这个 root 去中序遍历里确立左右子树的范围。但是代码依旧写不出来，因为感觉写一个至少六个入参的递归函数总觉得哪里都会出错。后面看了 discussion 后恍然大悟，没有必要死死卡在原数组上，直接根据之前的信息生成左右子数组，进行递归调用即可，代码如下：

class Solution {
    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        if (preorder.isEmpty() || inorder.isEmpty()) {
            return null
        }
        if (preorder.size == 1) {
            return TreeNode(preorder[0])
        }
        val result = TreeNode(preorder[0])
        val rootIndex = inorder.indexOf(preorder[0])
        result.left = buildTree(
            preorder.sliceArray(1..rootIndex),
            inorder.sliceArray(0 until rootIndex)
        )
        result.right = buildTree(
            preorder.sliceArray(rootIndex + 1..preorder.lastIndex),
            inorder.sliceArray(rootIndex + 1..inorder.lastIndex)
        )
        return result
    }
}