演算法筆記：樹 (Tree)

Gary Huang

Published in

Dublin so code

10 min readAug 17, 2020

沒想到演算法筆記也到了第五篇了（拭淚），每次都要好好把內容吸收才能寫出作業，小心得：大部分時候解不出 leetcode 題目是根本就不知道題目後面的概念，與其想破頭不如先讀理論再來解題目。

Tree 是一種資料結構，由 parent & children , node, root node 三個概念組成

樹的最根本特徵就是：在樹的結構裡，只有一個root(樹根)，並且不存在cycle。
此特徵將衍生出另外兩項等價的性質：

在樹中若要從root尋找特定node，一定只存在一條路徑(path)。
每個node只會有一個parent。

若樹的node只有指向left subtree(左子樹)與right subtree(右子樹)時，又稱為Binary Tree(二元樹)

透過 new 它會幫我們建立一個物件，然後裡面有 TreeNode 這個 function 裡面的內容，並且變成了屬性名稱和屬性值，也就是 root.val == 1，root.right == 2，root.left == 3。

Full & Complete Binary Tree

有兩類Binary Tree十分常見，分別為Full Binary Tree以及Complete Binary Tree。
(這裡不知該翻作「完滿二元樹」還是「完整二元樹」，所以就不做翻譯當作專有名詞，請見諒。)

A. Full Binary Tree:

如圖三所示，一棵Full Binary Tree(或稱作Perfect Binary Tree)具有以下性質：

所有internal node都有兩個subtree(也就是兩個child pointer)；
所有leaf node具有相同的level(或相同的height)。

由以上性質能夠推論出：

若一棵Full Binary Tree的leaf node之level為nn，整棵樹共有2n−12n−1個node。
例如，若leaf node的level為4，整棵樹共有15個node。

並且，每個node與其child有以下關係：

第ii個node的left child之index為 2i2i；
第ii個node的right child之index為 2i+12i+1；
除了root之parent為NULL之外，第ii個node的parent之index為 ⌊i2⌋⌊i2⌋ 。

B. Complete Binary Tree:

若一棵樹的node按照Full Binary Tree的次序排列(由上至下，由左至右)，則稱此樹為Complete Binary Tree。

以圖四及圖五作說明：

圖四的樹共有10個node，且這十個node正好填滿Full Binary Tree的前十個位置，則此樹為Complete Binary Tree。

圖五的樹共有11個node，但是第11個node(K)應該要是第5個node(E)的child，因此，此樹並非Complete Binary Tree。

Javascript 的 Object 建立

當我們使用 new 這個關鍵字時，實際上會先有一個空的物件被建立。接著 TreeNode 這個函式會被執行（invoke）。我們知道當函式執行的時候，在 execution context 中會有 this 被建立，而當我們使用 new 的時候，函式裡面的 this 會被指定成剛剛所建立的那個空物件。所以當執行 TreeNode 這個 function，執行到 this.firstName 和 this.lastName 時，因為 this 現在指稱的是那個空物件，所以實際上是在幫這個空物件賦予屬性名稱和屬性值。在這樣的過程中，只要這個函式建構式 TreeNode 沒有指定 return 為其他物件，它就會直接回傳給我們這個新建立的物件。接著讓我們透過程式碼來更清楚的了解這個執行的過程：

透過 new 會幫我們建立一個空的物件

現在我把我們原本的程式碼改成這樣：

function TreeNode(){
  console.log(this);
}const root = new TreeNode();

這時候程式碼回傳的結果如下，表示的確在執行這個程式的過程中幫我們建立了一個新的空物件：

TreeNode {}

函式的最後若return其他物件，則原新物件內容會被覆蓋

現在，讓我們把原本的程式碼稍微做如下修改，增加第六行的內容：

function TreeNode(val){
  this.val = val;
  this.right = this.left = null;
  return  {"RETURN":"原本this的內容就不會被回傳"};
}const root = new TreeNode();
console.log(root)

回傳的結果如下，原本被建立的新物件不會被回傳，而是回傳我們最後return給它的內容：

Object {"RETURN":"原本this的內容就不會被回傳"}

function constructor 的實際應用

由上面的方法，我們可以透過 function 的方式來建立一個新的物件，如果我們想要建立出同屬性名稱但不同屬性值的物件內容，我們可以把物件的屬性值變成參數，如此就能透過此 function constructor 建立出許多不同的物件：

function TreeNode (val) {
  this.val = val;
  this.right = this.left = null;
}const root = new TreeNode(1);
console.log(root);
var root_left = new TreeNode(2);
console.log(root_left);

如此，我們就可以透過同一個函式建構式建立出很多不同的物件：

TreeNode {val: 1, right: null, left:null}
TreeNode {val: 2, right: null, left:null}

此外，我們會把根據建構子（constructor）所建立出來的物件稱作是實例（instance）。

注意！如果我們忘了加上關鍵字 new

這裡有一個地方我們需要非常留意，如果你在程式撰寫的過程當中，忘記加上 new 這個關鍵字的話，例如：

const root = TreeNode(1);
console.log(root);

如此，因為 JavaScript 不知道你是要執行這個程式，還是要根據這個 function 去建立object，因次最後回傳 undefined 的結果。

BST 三種 traversal 方式

左中右：輸出最左邊的 node 再來是這個 node 的 parent 再來是右邊的 child node

BST 題目示範

Leetcode

Insert into a Binary Search Tree - LeetCode

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of…

leetcode.com

Solution: (Recursion)

Time complexity: O(logn ~ n)
Space complexity: O(logn ~ n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {
    // empty tree case:
    if (root === null) return new TreeNode(val);
    if (val > root.val) {
        root.right = insertIntoBST(root.right, val);
    } else {
        root.left = insertIntoBST(root.left, val);
    }
    return root;
};