二叉搜索樹找到，如果值存在

Question

努力學習樹節點...

Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree. 

Write a function that checks if a given binary search tree contains a given value. 

For example, for the following tree: 

n1 (Value: 1, Left: null, Right: null) 
n2 (Value: 2, Left: n1, Right: n3) 
n3 (Value: 3, Left: null, Right: null) 
Call to Contains(n2, 3) should return true since a tree with root at n2 contains number 3. 

到目前爲止IV得了......

public class BinarySearchTree 
    { 
     public static bool Contains(Node root, int value) 
     { 
      foreach (var v in root) 
      { 
       if (root.Value == value) 
       { 
        //value found return true 
       } 
      } 
     } 

     public static void Main(string[] args) 
     { 
      Node n1 = new Node(1, null, null); 
      Node n3 = new Node(3, null, null); 
      Node n2 = new Node(2, n1, n3); 

      Console.WriteLine(Contains(n2, 3)); 
     } 
    } 

但根標記爲不可用，如果我做根。我得到選項tostring，value，left，right。

我不能像列表那樣遍歷節點嗎？ 如何檢查在根中是否有值？ 謝謝

---

UPDATE 稀釋是OK ...感謝您的答覆juharr所以我已經更新了我的代碼...

public static bool Contains(Node root, int value) 
      { 
        if (root.Value == value) 
        { 
         return true; 
        } 
        else if (root.Value > value) 
        { 
         if (root.Right == null) 
         { 
          Contains(root.Left, value); 
         } 
         Contains(root.Right, value); 
        } 
        else //(root.Value < value) 
        { 
         if (root.Left == null) 
         { 
          Contains(root.Right, value); 
         } 

         Contains(root.Left, value); 
        } 

       return false; 
      } 

但是在第二輪循環根null並導致崩潰？

Answer 1

你靠近，但是這是你真正想要的

public static bool Contains(Node root, int value) 
{ 
    if (root == null) return false; 
    if (root.Value == value) return true; 
    if (root.Value > value) return Contains(root.Left, value); 
    return Contains(root.Right, value); 
} 

所以如果root是null則沒有號碼所以你返回false。然後檢查值是否匹配，如果是，則返回true。然後，如果root的值較大，則返回左子樹上遞歸調用的結果。最後，您只需在右子樹上返回遞歸調用的結果，因爲此時您知道根值較小。

Answer 2

我不能像列表一樣遍歷節點嗎？

您可以迭代通過BST - 使用堆棧傳遞過來的子節點將與幫助（如證明here）。因此，您可以將root的孩子放入堆疊中，然後將其值與您的目標value進行比較。

隨着中說，該說是更直觀的方式來處理這將是遞歸的 - 在理論上你會檢查當前節點的值，然後遞歸調用Contains - 它傳遞當前節點的right或left孩子，直到你找到你的目標Value，或不。

在這兩種方法中，你要利用你的問題指出了BST的優勢：

二叉搜索樹（BST）是二叉樹，其中每個節點的值大於或等於該節點左子樹中所有節點中的值，並且小於該節點右子樹中所有節點中的值。

通過「切斷」你知道你並不需要（與由於當前節點的價值，你的目標value）檢查值考慮到這一點，你就可以實現它在O(log n)時間。