Den kleinsten gemeinsamen Vorfahren in einem BST mit Swift 3 finden, der jedes Mal 0 zurückgibt

Question

Ich implementiere einen Algorithmus, um die LCA eines BST mit Swift 3 zurückzugeben. Ich habe jedoch Probleme mit den Optionals, sobald ich einige Testwerte laufen lasse Ich werde jedes Mal Null. Mein Test sollte 12.

Die BST sieht wie folgt zurück:

   20 

     8   22 

    4   12 

     10  14 

Implementierung

class Node { 
    var value: Int 
    var leftChild: Node? 
    var rightChild: Node? 

    init (value: Int) { 
     self.value = value 
    } 
} 

class BinarySearchTree { 

    var root: Node? 

    /* Function to find LCA of n1 and n2. The function assumes that both 
     n1 and n2 are present in BST */ 
    func findLCA(node: Node?, n1: Int, n2: Int) -> Node? { 
     if node == nil { 
      return nil 
     } 

     //traverse left: n1 and n2 are smaller than root 
     if (node!.value > n1 && node!.value > n2) { 
      print("left: n1: \(n1) n2: \(n2) node \(node!.value)") 
      return findLCA(node: node?.leftChild, n1: n1, n2: n2) 
     } 

     //traverse right: n1 and n2 are greater than root 
     if (node!.value < n1 && node!.value < n2) { 
      print("right: n1: \(n1) n2: \(n2) node \(node!.value)") 
      return findLCA(node: node?.rightChild, n1: n1, n2: n2) 
     } 

     return node 
    } 

} 

var tree = BinarySearchTree() 
tree.root? = Node(value: 20) 
tree.root?.leftChild = Node(value: 8) 
tree.root?.rightChild = Node(value: 22) 
tree.root?.leftChild?.leftChild = Node(value: 4) 
tree.root?.leftChild?.rightChild = Node(value: 12) 
tree.root?.leftChild?.rightChild?.leftChild = Node(value: 10) 
tree.root?.leftChild?.rightChild?.rightChild = Node(value: 14) 

var n1 = 10, n2 = 14; 
var t = tree.findLCA(node: tree.root, n1: n1, n2: n2) 
print("LCA of \(n1) and \(n2) is \(t?.value)") 

Ausgabe

LCA von 14 und 8 ist gleich Null

Compilieren Nachricht:

solution.swift: 53: 35:

Warnung: string Interpolation eine Debug-Beschreibung für einen optionalen Wert erzeugt; Wolltest du das explizit machen?

print ("LCA von (n1) und (n2) (t? .value)")

Answer 1

ändern

tree.root? = Node(value: 20) 

zu

tree.root = Node(value: 20) 

Und Ihr Druck aussehen soll wie:

print("LCA of \(n1) and \(n2) is \(t?.value ?? -1)") 

Dies wird -1 drucken, wenn Ihre Suche r Eurnns Null.