由遍历序列重构二叉树一题引发的思考
leetcode地址:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
在leetcode训练时,发现虽然通过了OJ,但是有一处代码(下图划红线处)不严谨,如果二叉树中存在val
数值相同的节点则会导致错误
于是我将此行代码改正,并重复提交,却发现Time Complexity
和Space 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#