[IT技術30篇挑戰] 資料結構和演算法實作 DAY10

章節連結

二元樹
LeetCode 練習記錄
系列文章

二元樹 (Binary Tree) 是資料結構的一種，最根部稱為 (root)。在每一個節點(node)可以有兩個子節點，每個子節點可以再依照此規則發展下去。葉節點為整棵樹的終端，其下方沒有其他節點了。至於階層(橫向來看)的話，會發現每一階層最多能放的數量是 2 的 n 次方。

二元樹

function BinarySearchTree(){
	/*to set node structure*/
	let Node = function(key){
		this.key = key
		this.left = null
		this.right = null
	}
	/*to set root*/
	let root = null

	this.insert = (key)=>{
		let newNode = new Node(key)
		let insertNode = (node,newNode)=>{
			if(newNode.key<node.key){
				if(node.left === null){
					node.left = newNode
				}else{
					insertNode(node.left,newNode)
				}
			}else{
				if(node.right===null){
					node.right = newNode
				}else{
					insertNode(node.right,newNode)
				}
			}
		}

		if(root===null){
			root = newNode
		}else{
			insertNode(root,newNode)
		}

	}

	/*find min, follow left part of the tree*/
	this.min = ()=>{
		let minNode = (node)=>{
			if(node){
				while(node && node.left !== null){
					node = node.left
				}
				return node.key
			}
			return null
		}
		return minNode(root)
	}

	/*find max, follow right part of the tree*/
	this.max = ()=>{
		let minNode = (node)=>{
			if(node){
				while(node && node.right !== null){
					node = node.right
				}
				return node.key
			}
			return null
		}
		return minNode(root)
	}

	/*find particular value whether it is existed*/
	this.search = (key)=>{
		let searchNode = (node,key)=>{
			if(node ===null){
				return false
			}
			if(key<node.key){
				return searchNode(node.left,key)
			}else if(key>node.key){
				return searchNode(node.right,key)
			}else{
				return true
			}
		}
		return searchNode(root,key)
	}
}

let tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.insert(6)
console.log(tree.min()) // 3
console.log(tree.max()) // 25
console.log(tree.search(12)) //true
console.log(tree.search(100)) //false

100

101

102

function BinarySearchTree(){

/*to set node structure*/

let Node = function(key){

this.key = key

this.left = null

this.right = null

}

/*to set root*/

let root = null

this.insert = (key)=>{

let newNode = new Node(key)

let insertNode = (node,newNode)=>{

if(newNode.key<node.key){

if(node.left === null){

node.left = newNode

}else{

insertNode(node.left,newNode)

}

}else{

if(node.right===null){

node.right = newNode

}else{

insertNode(node.right,newNode)

}

if(root===null){

root = newNode

}else{

insertNode(root,newNode)

}

/*find min, follow left part of the tree*/

this.min = ()=>{

let minNode = (node)=>{

if(node){

while(node && node.left !== null){

node = node.left

}

return node.key

}

return null

}

return minNode(root)

}

/*find max, follow right part of the tree*/

this.max = ()=>{

let minNode = (node)=>{

if(node){

while(node && node.right !== null){

node = node.right

}

return node.key

}

return null

}

return minNode(root)

}

/*find particular value whether it is existed*/

this.search = (key)=>{

let searchNode = (node,key)=>{

if(node ===null){

return false

}

if(key<node.key){

return searchNode(node.left,key)

}else if(key>node.key){

return searchNode(node.right,key)

}else{

return true

}

return searchNode(root,key)

}

let tree = new BinarySearchTree()

tree.insert(11)

tree.insert(7)

tree.insert(15)

tree.insert(5)

tree.insert(3)

tree.insert(9)

tree.insert(8)

tree.insert(10)

tree.insert(13)

tree.insert(12)

tree.insert(14)

tree.insert(20)

tree.insert(18)

tree.insert(25)

tree.insert(6)

console.log(tree.min()) // 3

console.log(tree.max()) // 25

console.log(tree.search(12)) //true

console.log(tree.search(100)) //false

LeetCode 練習記錄

// 100. Same Tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if( p === null && q === null) return true
    if( (p === null && q !==null) || (p !== null && q ===null)) return false
    
    if( p.val !== q.val) return false
    
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
};

// 110. Balanced binary tree
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if(root===null || (root.left===null && root.right === null)) return true
    
    let leftDepth = findDeep(root.left)
    let rightDepth = findDeep(root.right)
    let diff = Math.abs(leftDepth-rightDepth) <= 1
        
    if(diff){
        return isBalanced(root.left) && isBalanced(root.right)
    }else{
        return false
    }
    
    
};

function findDeep(root){    
    if(root === null) {
        return 0;
    }
    
    let deepLeft = 1+findDeep(root.left);
    let deepRight = 1+findDeep(root.right);

    return deepLeft > deepRight ? deepLeft:deepRight;
}