iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 27
0
Software Development

One Punch 一拳搞定前後端面試系列 第 27

[One Punch 一拳搞定前後端面試] DAY-27 -Binary Search Tree - Contains

  • 分享至 

  • xImage
  •  

Binary Search Tree Contains

找二元搜尋樹裡面的 node。

題目: 給一個值 x,請在 Binary Search Tree 內搜尋有無 x 並回傳該 node,若無則回傳 null。

本文同時發布於好讀整理版

想法

前幾篇提到有兩種(Depth First, Breadth First)方式可以遍歷(Traversal)整個 Tree,
那在這題情況適合哪一種呢?

想想看,我們的 root node 下來左邊比它自己小,右邊比它自己大,所以只要找其中一邊就好,
那就是 Depth First 會比較適合。

與前一篇 Insert 差不多作法。

底下我們用 recursion 方式來解決此問題。

JavaScript 實作

js

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  contains(data) {
    // 若是 root 直接回傳 node
    if(this.data === data){
      return this;
    }

    if (this.data < data && this.right) {
      return this.right.contains(data);
    } else if (this.data > data && this.left) {
      return this.left.contains(data);
    }

    // 上面條件都不符合,回傳 null
    return null;
  }

Java 實作

Java

class BinarySearchTree {

  class Node {
      int key;
      Node left, right;

      public Node(int item) {
          key = item;
          left = right = null;
      }
  }

  Node root;

  BinarySearchTree() {
      root = null;
  }

  public Node contains(Node root, int key) {

  if (root.key==key) {
      return root;
  }

  if (root.key > key){
    return contains(root.left, key);
  } else if (root.key < key){
    return contains(root.right, key);
  }

  return null
  }

}

今天的 找二元搜尋樹裡面的 node 就先到這邊,明天繼續有趣的題目...

敬請期待!!

本文同時發布於好讀整理版


上一篇
[One Punch 一拳搞定前後端面試] DAY-26 -Binary Search Tree - Insert
下一篇
[One Punch 一拳搞定前後端面試] DAY-28 - Bubble Sort
系列文
One Punch 一拳搞定前後端面試30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言