|
| 1 | +packageeasy; |
| 2 | + |
| 3 | +importclasses.TreeNode; |
| 4 | + |
| 5 | +publicclassClosestBinarySearchTreeValue { |
| 6 | + |
| 7 | +classGeneral_tree_solution { |
| 8 | +//this finished in 1 ms |
| 9 | +publicintclosestValue(TreeNoderoot,doubletarget) { |
| 10 | +if (root ==null) |
| 11 | +return0; |
| 12 | +doubledelta =Double.MAX_VALUE; |
| 13 | +returndfs(root,target,delta,root.val); |
| 14 | + } |
| 15 | + |
| 16 | +privateintdfs(TreeNoderoot,doubletarget,doubledelta,intclosestVal) { |
| 17 | +if (Math.abs(root.val -target) <delta) { |
| 18 | +closestVal =root.val; |
| 19 | +delta =Math.abs(root.val -target); |
| 20 | + } |
| 21 | +intleftVal =closestVal; |
| 22 | +if (root.left !=null) |
| 23 | +leftVal =dfs(root.left,target,delta,closestVal); |
| 24 | +intrightVal =closestVal; |
| 25 | +if (root.right !=null) |
| 26 | +rightVal =dfs(root.right,target,delta,closestVal); |
| 27 | +return (Math.abs(leftVal -target) >Math.abs(rightVal -target)) ?rightVal :leftVal; |
| 28 | + } |
| 29 | + } |
| 30 | + |
| 31 | +classBST_solution_recursive{ |
| 32 | +//we can tailor the solution to use the BST feature: left subtrees are always smaller than the root the right subtrees |
| 33 | +//this finished in 0 ms |
| 34 | +publicintclosestValue(TreeNoderoot,doubletarget) { |
| 35 | +if(root ==null)return0; |
| 36 | +returndfs(root,target,root.val); |
| 37 | + } |
| 38 | + |
| 39 | +privateintdfs(TreeNoderoot,doubletarget,intminVal) { |
| 40 | +if(root ==null)returnminVal; |
| 41 | +if(Math.abs(root.val -target) <Math.abs(minVal -target)){ |
| 42 | +minVal =root.val; |
| 43 | + } |
| 44 | +if(target <root.val){ |
| 45 | +minVal =dfs(root.left,target,minVal); |
| 46 | + }else { |
| 47 | +minVal =dfs(root.right,target,minVal); |
| 48 | + } |
| 49 | +returnminVal; |
| 50 | + } |
| 51 | + } |
| 52 | + |
| 53 | +classGeneral_tree_solution_more_concise{ |
| 54 | +publicintclosestValue(TreeNoderoot,doubletarget) { |
| 55 | +if(root ==null)return0; |
| 56 | +returndfs(root,target,root.val); |
| 57 | + } |
| 58 | + |
| 59 | +privateintdfs(TreeNoderoot,doubletarget,intminVal) { |
| 60 | +if (root ==null) |
| 61 | +returnminVal; |
| 62 | +if (Math.abs(root.val -target) <Math.abs(minVal -target)) { |
| 63 | +minVal =root.val; |
| 64 | + } |
| 65 | +minVal =dfs(root.left,target,minVal); |
| 66 | +minVal =dfs(root.right,target,minVal); |
| 67 | +returnminVal; |
| 68 | + } |
| 69 | + } |
| 70 | + |
| 71 | +classBST_solution_iterative{ |
| 72 | +publicintclosestValue(TreeNoderoot,doubletarget) { |
| 73 | +longminVal =Long.MAX_VALUE; |
| 74 | +while(root !=null){ |
| 75 | +if(Math.abs(root.val -target) <Math.abs(minVal -target)){ |
| 76 | +minVal =root.val; |
| 77 | + } |
| 78 | +if(target <root.val)root =root.left; |
| 79 | +elseroot =root.right; |
| 80 | + } |
| 81 | +returnminVal ==Long.MAX_VALUE ?0 : (int)minVal; |
| 82 | + } |
| 83 | + } |
| 84 | +} |