symetric-tree.js (2019B)
1 //Go through a binary tree and check if it is symetrical 2 //The time complexity of this code is O(n) where n is the number of 3 //nodes in the tree. This algorithm uses BFS to search layer by layer and verify 4 //that each layer is symetrical from the left and the right. 5 6 /** 7 * Definition for a binary tree node. 8 * function TreeNode(val, left, right) { 9 * this.val = (val===undefined ? 0 : val) 10 * this.left = (left===undefined ? null : left) 11 * this.right = (right===undefined ? null : right) 12 * } 13 */ 14 /** 15 * @param {TreeNode} root 16 * @return {boolean} 17 */ 18 let arr = new Array(); 19 var isSymmetric = function(root) { 20 let queue = []; 21 queue.push(root); 22 while(queue.length != 0){ 23 let queue_len = queue.length; 24 let valid = false; 25 for(let i = 0 ; i < queue_len ; ++i){ 26 let current_node = queue.pop(); 27 if(current_node != null){ 28 if(current_node.left != null){ 29 queue.unshift(current_node.left); 30 valid = true; 31 } 32 else{ 33 let tree1 = new TreeNode(); 34 tree1.val = -1; 35 queue.unshift(tree1); 36 } 37 if(current_node.right != null){ 38 queue.unshift(current_node.right); 39 valid = true; 40 } 41 else{ 42 let tree = new TreeNode(); 43 tree.val = -1; 44 queue.unshift(tree); 45 } 46 } 47 } 48 if(valid != true){ 49 return true; 50 } 51 if(queue.length != -1){ 52 if(symetrical(queue) == false){ 53 return false; 54 } 55 } 56 } 57 return true; 58 }; 59 let symetrical = (arr) => { 60 if(arr.length%2 != 0){ 61 return false; 62 } 63 for(let i = 0 ; i < arr.length / 2 + 1; ++i){ 64 if(arr[i].val != arr[arr.length - i - 1].val){ 65 return false; 66 } 67 } 68 return true; 69 }