由遍历序列重构二叉树一题引发的思考

leetcode地址:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

在leetcode训练时,发现虽然通过了OJ,但是有一处代码(下图划红线处)不严谨,如果二叉树中存在val数值相同的节点则会导致错误

图片说明

于是我将此行代码改正,并重复提交,却发现Time ComplexitySpace Complexity都恶化了

图片说明

what happened?

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null ||
                inorder.length == 0 || postorder.length == 0
                || inorder.length != postorder.length) return null;

        int end = inorder.length - 1;
        return build(inorder, 0, end, postorder, 0, end);
    }

    private TreeNode build(int[] inorder, int i, int j, int[] postorder, int m, int n){
        if(i == j) return new TreeNode(inorder[i]);
        int val = postorder[n];
        int index = index(inorder, i, j, val);
        if(index == -1) throw new RuntimeException("invalid input");

        TreeNode root = new TreeNode(val);
        int lefts = index - i, rights = j - index;
        root.left = lefts == 0 ? null : build(inorder, i, i + lefts - 1, postorder, m, m + lefts - 1);
        root.right = rights == 0 ? null : build(inorder, i + lefts + 1, j, postorder, m + lefts, n - 1);
        return root;
    }

    private int index(int[] arr, int begin, int end, int val){
        for(int i = begin ; i <= end; i++)
            if(arr[i] == val) return i;
        return -1;
    }
}
#leetcode##Java#
全部评论
题目写的假设没有重复呀
点赞 回复
分享
发布于 2019-11-21 13:15
根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。
点赞 回复
分享
发布于 2019-11-21 13:20
小红书
校招火热招聘中
官网直投

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务