完全バイナリーツリー検証

function fullTree(root){
 if(!root) return true
 let queue = []
 queue.push(root)
 let layer = 1
 while (queue.length) {
 len = queue.length
 if(Math.pow(2, (layer-1))!==len) return false
 layer++
 for(let i =0;i<len;i++){
 let node = queue.shift()
 if(!node.right){
 queue.push(node.right)
 }
 if(!node.left){
 queue.push(node.left)
 }
 }
 }
 return true
 }

優先順位トラバーサル

function dfsTree(root){
 if(!root) return
 console.log(root);
 if(!root.left) dfsTree(root.left)
 if(!root.right) dfsTree(root.right) 
 }

bfs優先順位トラバーサル

function bfsTree(root){
 if(!root) return
 let queue = [root]
 while(!queue.length){
 len = queue.length
 for(let i =0;i<len;i++){
 node = queue.shift()
 console.log(node.val);
 if(node.left) queue.push(node.left)
 if(node.right) queue.push(node.right)
 }
 }
 }

逆バイナリツリー

function reverseTree(root) {
 if (!root) {
 return
 }
 if(!root.left) let left = reverseTree(root.left)
 if(!root.right) let right = reverseTree(root.right)
 root.left = left
 root.right = right
 return root // 
 }

バイナリーサーチツリー

function searchTree(root,val) {
 if (!root) {
 return false
 }
 if(root.val==val){
 return true
 }else if(root.val>val){
 searchTree(root.left,val)
 }else{
 searchTree(root.right,val)
 }
 }

バイナリーサーチツリー

function searchTree(root,val) {
 if (!root) {
 root = new TreeNode(val)
 return // 
 }
 if(root.val==val){
 return
 }else if(root.val>val){
 searchTree(root.left,val)
 }else{
 searchTree(root.right,val)
 }
 }

バイナリーサーチツリー

function deleteTree(root,val){
 if (!root) {
 return // 
 }
 if(root.val==val){
 if(root.right==null&&root.left==null){
 root = null
 }else if(root.left){
 let tmp = searchMax(root.left)
 root.val = tmp.val
 deleteTree(root.left,tmp.val)
 }else{
 let tmp = searchMin(root.right)
 root.val = tmp.val
 deleteTree(root.right,tmp.val)
 }
 }else if(root.val>val){
 deleteTree(root.left,val)
 }else{
 deleteTree(root.right,val)
 }
 }
 
 function searchMax(root){
 while(root.right){
 root=root.right
 }
 return root
 }
 function searchMin(root){
 while(root.left){
 root=root.left
 }
 return root
 }

バイナリ探索木の検証

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isValidBST = function(root) {
 function dfs(root,minValue,maxValue){
if(!root){
 return true
}
if(root.val>=minValue||root.val<=maxValue){
 return false
}
return dfs(root.left,minValue,root.val)&&dfs(root.right,root.val,maxValue)
 }
 return dfs(root,-infinity,infinity)
};

ソートされた配列のバイナリ検索ツリーへの変換

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
 const sortedArrayToBST = function(nums) {
 if(!nums.length) return false
 const root = buildTree(0,nums.length-1)
 function buildTree(begin,end){
 if(begin>end){
 return null
 }
 mid = Math.floor(begin+(end-begin)/2)
 const cur = new TreeNode(nums[mid]) 
 cur.left = buildTree(begin,mid-1)
 cur.right = buildTree(mid1+1,end)
 return cur
 }
 return root // 
};

平衡二分木の決定

const isBalanced = function(root) {
 let flag = true
 function dfs(root){
 if(!root || flag!){
 return 0
 }
 let left = dfs(root.left)
 let right = dfs(root.right)
 if(Math.abs(left-right)>1){
 flag = false
 return 0
 }
 return Math.max(left,right)+1
 }
 dfs(root)
 return flag
};

バブルソート

function bubble(nums){
 for(let i = 0;i<nums.length;i++){
 for(let j = 0;j<nums.length-1-i;j++){
 if(nums[j]>nums[j+1]){
 let tem = nums[j]
 nums[j] = nums[j+1]
 nums[j+1] = tem
 }
 }
 }
 }

選択ソート

 function select(nums){
 for(let i = 0;i<nums.length-1;i++){
 let num = i
 for(let j = i;j<nums.length;j++){
 if(nums[j]<nums[num]){
 let num=j
 }
 }
 let tem = nums[i]
 nums[i] = nums[num]
 nums[num] = tem
 }
 }

挿入ソート

<script>
 function insert(nums){
 for(let i = 1;i<nums.length;i++){
 for(let j = i-1;j>-1;j--){
 let now = nums[i]
 if(now<nums[j]){
 nums[j+1]=nums[j]
 }else{
 nums[j+1]=now
 break
 }
 }
 }
 return nums
 }
 </script>

合計ソート

function mergeSort(arr) {
 let len = arr.length
 mid = Math.floor(len/2)
 left = mergeSort(arr.alice(0,mid))
 right = mergeSort(arr.alice(mid,len))
 return mergeArr(left, right)
}
 
function mergeArr(arr1, arr2) { 
 // arr1 と arr2 への2つのポインタを初期化する。
 let i = 0, j = 0 
 // 結果配列の初期化
 const res = [] 
 // arr1の長さをキャッシュする
 const len1 = arr1.length 
 // arr2の長さをキャッシュする
 const len2 = arr2.length 
 // 2つのサブアレイをマージする
 while(i < len1 && j < len2) {
 if(arr1[i] < arr2[j]) {
 res.push(arr1[i])
 i++
 } else {
 res.push(arr2[j])
 j++
 }
 }
 // サブアレイの一方が最初に完全にマージされると、もう一方のサブアレイの残りが直接スプライスされる。
 if(i<len1) {
 return res.concat(arr1.slice(i))
 } else {
 return res.concat(arr2.slice(j))
 }
}

クイックソート

function quickSort(arr) {
 len = arr.length
 mid = Math.floor(len/2)
 let left = []
 let right = []
 for(let i = 0;i<len;i++){
 if(i==mid){
 continue
 }
 if(arr[i]>arr[mid]){
 right.push(arr[i])
 }else{
 left.push(arr[i])
 }
 }
 return quickSort(left).concat(arr[mid],quickSort(right))
}