剑指Offer:面试题07.重建二叉树

本文最后更新于 732 天前，其中的信息可能已经有所发展或是发生改变。

1.要点

• 二叉树遍历
• 重复在数组中查找某个数时（重复 查找=二重循环），应考虑是否可以用map

2.题目

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

3.示例

给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

代码语言：javascript复制

    3
   / 
  9  20
    /  
   15   7

4.限制：

0 <= 节点个数 <= 5000

5.代码

代码语言：javascript复制

public TreeNode buildTree(int[] preorder, int[] inorder) {
        return preorder.length == 0 ? null : buildNode(preorder, inorder);
    }

    public TreeNode buildNode(int[] preorder, int[] inorder) {
        int rootNodeIndex = -1;
        int rootNodeValue = 0;
        Map<Integer,Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i  ) {
            inorderMap.put(inorder[i],i);
        }

        for (int i = 0; i < preorder.length; i  ) {
                if (null != inorderMap.get(preorder[i])) {
                    rootNodeIndex = inorderMap.get(preorder[i]);
                    rootNodeValue = preorder[i];
                    break;
                }
        }

        TreeNode treeNode = new TreeNode(rootNodeValue);
        treeNode.left = rootNodeIndex > 0 ?
                buildNode(preorder, Arrays.copyOfRange(inorder, 0, rootNodeIndex)) :
                null;
        treeNode.right = rootNodeIndex < inorder.length - 1 ?
                buildNode(preorder, Arrays.copyOfRange(inorder, rootNodeIndex   1, inorder.length)) :
                null;
        return treeNode;
    }

Post Views: 323

编程算法 二叉树

0 人点赞