[筆記] Master The Coding Interview – 14

Posted on2020-12-122020-12-07AuthorANDY LIEN

章節連結

課程相關資訊
範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Tree」關於樹的第二部分簡介。

課程相關資訊

[連結]：https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/

課程對應章節：126~129

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

範例程式碼

Binary Search Tree 非常適合用於搜尋，運用 Parent / Children 的功能來找節點
[ 特色 ]
1. 往右走的子節點，數值會比父節點大；反之亦然
2. 若為 Unbalanced ，那就會使 BigO 變為 O (n) ，類似成 Linked List 的結構
3. Ordered / Flexible Size，至少比 O (n) 好。不過沒有 O (1) 的操作

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  insert(value){
    //Code here
    const newNode = new Node(value)
    if(!this.root){
      this.root = newNode
    }else{
      let currentNode = this.root
      while(true){
        if(value < currentNode.value){
          if(!currentNode.left){
            currentNode.left = newNode
            return this
          }
          currentNode = currentNode.left
        }else{
          if(!currentNode.right){
            currentNode.right = newNode
            return this
          }
          currentNode = currentNode.right
        }
      }
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
JSON.stringify(traverse(tree.root))

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

class Node {

constructor(value){

this.left = null;

this.right = null;

this.value = value;

}

}

class BinarySearchTree {

constructor(){

this.root = null;

}

insert(value){

//Code here

const newNode = new Node(value)

if(!this.root){

this.root = newNode

}else{

let currentNode = this.root

while(true){

if(value < currentNode.value){

if(!currentNode.left){

currentNode.left = newNode

return this

}

currentNode = currentNode.left

}else{

if(!currentNode.right){

currentNode.right = newNode

return this

}

currentNode = currentNode.right

}

}

}

}

}

const tree = new BinarySearchTree();

tree.insert(9)

tree.insert(4)

tree.insert(6)

tree.insert(20)

tree.insert(170)

tree.insert(15)

tree.insert(1)

JSON.stringify(traverse(tree.root))

// 9

// 4 20

//1 6 15 170

function traverse(node) {

const tree = { value: node.value };

tree.left = node.left === null ? null : traverse(node.left);

tree.right = node.right === null ? null : traverse(node.right);

return tree;

}

相關文章

★全文分享★ [筆記] Master The Coding Interview – 16

[筆記] Master The Coding Interview – 16

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 15

[筆記] Master The Coding Interview – 15

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 13

[筆記] Master The Coding Interview – 13

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 12

[筆記] Master The Coding Interview – 12

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 11

[筆記] Master The Coding Interview – 11

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 10

[筆記] Master The Coding Interview – 10

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 9

[筆記] Master The Coding Interview – 9

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 8

[筆記] Master The Coding Interview – 8

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 7

[筆記] Master The Coding Interview – 7

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 6

[筆記] Master The Coding Interview – 6

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 5

[筆記] Master The Coding Interview – 5

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 4

[筆記] Master The Coding Interview – 4

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 3

[筆記] Master The Coding Interview – 3

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 2

[筆記] Master The Coding Interview – 2

這篇是 Udemy 上的知名課程 – Master the Coding

★全文分享★ [筆記] Master The Coding Interview – 1

[筆記] Master The Coding Interview – 1

工程師的面試中，不免俗的會遇見用各種

按讚加入粉絲團

延伸閱讀

Blogimove部落格搬家技術服務