章節連結
二元樹 (Binary Tree) 是資料結構的一種，最根部稱為 (root)。在每一個節點(node)可以有兩個子節點，每個子節點可以再依照此規則發展下去。葉節點為整棵樹的終端，其下方沒有其他節點了。至於階層(橫向來看)的話，會發現每一階層最多能放的數量是 2 的 n 次方。
二元樹
|
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 練習記錄
|
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 59 60 |
// 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; } |
