Advertisement
sanya5791

Construct Binary Search Tree from Preorder Traversal (wrong solution))

Aug 6th, 2021
1,555
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 1.64 KB | None | 0 0
  1. /**
  2.  * Example:
  3.  * var ti = TreeNode(5)
  4.  * var v = ti.`val`
  5.  * Definition for a binary tree node.
  6.  * class TreeNode(var `val`: Int) {
  7.  *     var left: TreeNode? = null
  8.  *     var right: TreeNode? = null
  9.  * }
  10.  */
  11. class Solution {
  12.    
  13.     fun bstFromPreorder(preorder: IntArray): TreeNode? {
  14.         if(preorder.size == 0) return null
  15.        
  16.         val root = TreeNode(preorder[0], null, null)
  17.         buildBst(root, min = Int.MIN_VALUE, max = Int.MAX_VALUE, preorder = preorder, nodeIdx = 1)
  18.        
  19.         return root
  20.     }
  21.    
  22.     private fun buildBst(root: TreeNode, min: Int, max: Int, preorder: IntArray, nodeIdx: Int) {
  23.         println("root=${root.`val`}/${root.left}/${root.right}, min=$min, max=$max, node=${preorder[nodeIdx]}")
  24.         if(nodeIdx >= preorder.size) return
  25.        
  26.         val nodeVal = preorder[nodeIdx]//5
  27.         val node = TreeNode(nodeVal, null, null)
  28.        
  29.         if(nodeVal > min && nodeVal < root.`val`) {
  30.             root.left = node
  31.             buildBst(root = node, min = min, max = root.`val`, preorder = preorder, nodeIdx = nodeIdx + 1)
  32.         } else if(nodeVal > root.`val` && nodeVal < max) {
  33.             root.right = node
  34.             buildBst(root = node, min = root.`val`, max = max, preorder = preorder, nodeIdx = nodeIdx + 1)
  35.         } else {
  36.  
  37. /*error is here. I cannot return to parent boundaries
  38. input: [8,5,1,7,10,12]
  39.  
  40. stdout:
  41. root=8/null/null, min=-2147483648, max=2147483647, node=5
  42. root=5/null/null, min=-2147483648, max=8, node=1
  43. root=1/null/null, min=-2147483648, max=5, node=7
  44.  
  45. actual output: [8,5,null,1]
  46. expected output: [8,5,10,1,7,null,12]
  47. */
  48.         }
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement