アルゴリズム学習を行った後,学んだ内容を整理した.

BFS

主に最短パスを探すために使用されます.

templete

class BFS() {
    constructor(val) {
	let val = val;
	let left = null || left;
	let right = null || right;
    }
}

function bfsTemplate(root) {
    const queue = [[root]];	// queue declaration
    const result = [[root.val]];
    while(queue.length > 0) {
	const curLevelElement= queue.shift(); // first element in the queue; /// [3], [9, 20], [15, 7]
        // queue = []
	const nextLevel = [];
	// curLevelElement = [3]
	for(let i = 0; i < curLevelElement.length; i++) { // 9 , 20
	    const curNode = curLEvelElement[i]; // 3-root, 9, 20
	    if(curNode.left) { // 15
		nextLevel.push(curNode.left);
	    }
	    if(curNode.right) { // 7
		nextLevel.push(curNode.right);
	    }
	}
	//nextLevel = [15, 7]
	if(nextLevel.length === 0) return;
	else queue.push([]);
	//queue = [[9, 20]]
    }
    return
}

DFS

よく使う.特定のパスを求めるために使用されます.

recursive

どの値が含まれているか分からない場合に使用します.
前列(preorder)、中列(order)、後列(postorder)

前衛ツアー:自身-左-右

中尉巡回:左-自身-右

後列:左-右-自身

時間の複雑さ:O(N)->すべての要素を探索します.
空間複雑度:O(d)->d=depth-stackが使用されるため.maximum call stack
worst space: O(N)

iterative

バイナリ検索ツリーで有効なBSTに使用されます.
すなわち,木の値が固定で規則的である場合に用いる.
正しい値を使用します.
時間の複雑さ:O(logn)->下に下がるほど半分少なくなります.
空間複雑度:O(1)

templete

recursive

function main (root) {
const result = []
    dfsTemplate(root, result);
}
function dfsTemplate(curNode, result)  {
	// base case when do we stop the recursion
    if(curNode === null) return;

    dfsTemplate(curNode.left);
    dfsTemplate(curNode.right);
    result.push(curNode.val);
}

iterative

function dfsIterativeTemplate(root, target) {
    const curNode = root; // 6
    while(curNode) {
	if(curNode.val > target) {
	    curNode = curNode.left; // 4
	} else {
	    curNode = curNode.right // 8
	}

    }
}

深さと高さの違い

depth:奥行き.ルートからリーフノードへheight:高さ.リーフノードからルートへ
普通は深さを書きますが、難しい問題はheightを書きます.

コード#コード#

var maxDepth = function(root) {
    
    // base case ==> edge case
    if(root === null) return 0;
    const depth = [0];
    depthRecursive(root, depth, 1)
    return depth[0];
    //return heightRecursive(root).height;
};

// top to bottom approach
function depthRecursive(curNode, depth, curDepth) {
    if(!curNode.left && !curNode.right) {
        depth[0] = Math.max(depth[0], curDepth);
        return;
    }
    
    if(curNode.left) {
        depthRecursive(curNode.left, depth, curDepth + 1);
    }
    
    if(curNode.right) {
        depthRecursive(curNode.right, depth, curDepth + 1);
    }
    
    return;
    
}

/// bottom up approach
function heightRecursive(curNode) {
    if(curNode === null) {
        return {height: 0};
    }
    
    let left = heightRecursive(curNode.left);
    let right = heightRecursive(curNode.right);
    //console.log(left.height, right.height)
    
    return {height : Math.max(left.height, right.height) + 1};
}

topological sort

他のアルゴリズムをBFSまたはDFSと混合して使用する.
飛行機の乗り換え問題.