105. Construct Binary Tree from Preorder and Inorder Travers

发布时间：2020-12-14 05:13:21 所属栏目：大数据来源：网络整理

导读：/** * 105. Construct Binary Tree from Preorder and Inorder Traversal * * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ * * Given preorder and inorder traversal of a tree,construct the

/**
 * 105. Construct Binary Tree from Preorder and Inorder Traversal
 *
 * 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.

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

For example,given

preorder = [3,9,20,15,7]
inorder = [9,3,7]
Return the following binary tree:

3
/ 
9  20
/  
15   7
 * */

class Solution {

    class TreeNode(var `val`: Int = 0) {
        var left: TreeNode? = null;
        var right: TreeNode? = null;
    }

    fun buildTree(preorder: IntArray,inorder: IntArray): TreeNode? {
        if (preorder.isEmpty() || inorder.isEmpty())
            return null;
        val map = HashMap<Int,Int>();
        for ((index,element) in inorder.withIndex()) {
            map.put(element,index);
        }
        return help(preorder,preorder.size - 1,inorder,inorder.size - 1,map);
    }

    fun help(
        preorder: IntArray,pLeft: Int,pRight: Int,inorder: IntArray,iLeft: Int,iRight: Int,map: HashMap<Int,Int>
    ): TreeNode? {
        if (pLeft > pRight || iLeft > iRight)
            return null;
        val node = TreeNode(preorder[pLeft]);
        val rootIndex:Int = map.get(preorder[pLeft])!!;//not-null assertion operator:!! convert Int? to Int
        node.left = help(preorder,pLeft+1,pLeft+rootIndex-iLeft,iLeft,rootIndex-1,map);
        node.right = help(preorder,pLeft+rootIndex-iLeft+1,pRight,rootIndex+1,iRight,map);
        return node;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!