class TreeNode { val : any ; left : TreeNode ; right : TreeNode ; constructor ( val ) { this . val = val ; this . left = this . right = undefined ; } } class Tree < T > { root : TreeNode ; constructor ( data ) { let nodeList = [ ] ; for ( let i = 0 , len = data . length ; i < len ; i ++ ) { let node = new TreeNode ( data [ i ] ) ; nodeList . push ( node ) ; if ( i > 0 ) { let n = Math . floor ( Math . sqrt ( i + 1 ) ) ; let q = Math . pow ( 2 , n ) - 1 ; let p = Math . pow ( 2 , n - 1 ) - 1 ; let parent = nodeList [ p + Math . floor ( ( i - q ) / 2 ) ] ; if ( parent . left !== undefined ) { parent . right = node ; } else { parent . left = node ; } } } this . root = nodeList . shift ( ) ; nodeList . length = 0 ; } public inOrderTraversal ( root , array ) { if ( root ) { this . inOrderTraversal ( root . left , array ) ; array . push ( root . val ) ; this . inOrderTraversal ( root . right , array ) ; } return array ; } public inOrderTraversal2 ( root ) { let arr = [ ] ; let stack = [ ] ; let node = root ; while ( node || stack . length > 0 ) { if ( node ) { stack . push ( node ) ; node = node . left ; } else { node = stack . pop ( ) ; arr . push ( node . val ) ; node = node . right ; } } return arr ; } public preOrderTraversal ( root , array ) { if ( root ) { array . push ( root . val ) ; this . preOrderTraversal ( root . left , array ) ; this . preOrderTraversal ( root . right , array ) ; } return array ; } public preOrderTraversal2 ( root ) { let arr = [ ] ; let stack = [ ] ; stack . push ( root ) ; while ( stack . length > 0 ) { let node = stack . pop ( ) ; arr . push ( node . val ) ; if ( node . right !== undefined ) stack . push ( node . right ) ; if ( node . left !== undefined ) stack . push ( node . left ) ; } return arr ; } public postOrderTraversal ( root , array ) { if ( root ) { this . postOrderTraversal ( root . left , array ) ; this . postOrderTraversal ( root . right , array ) ; array . push ( root . val ) ; } return array ; } public postOrderTraversal2 ( root ) { let arr = [ ] ; let stack = [ ] ; let node = root ; let right = null ; while ( node || stack . length > 0 ) { if ( node ) { stack . push ( node ) ; node = node . left ; } else { node = stack [ stack . length - 1 ] ; if ( node . right === right || node . right === undefined ) { arr . push ( node . val ) ; right = node ; stack . pop ( ) ; node = null ; } else { node = node . right ; } } } return arr ; } public treeDepth ( root ) { return ( root === undefined || root . val === null ) ? 0 : Math . max ( this . treeDepth ( root . left ) , this . treeDepth ( root . right ) ) + 1 ; } public minDepth ( root ) { if ( root === undefined || root . val === null ) { return 0 ; } let left = this . minDepth ( root . left ) ; let right = this . minDepth ( root . right ) ; return ( left && right ) ? 1 + Math . min ( left , right ) : 1 + left + right ; } public isBalanced ( root ) { if ( ! root || root . val === null ) { return true ; } let left = this . isBalanced ( root . left ) ; let right = this . isBalanced ( root . right ) ; if ( left === false || right === false || Math . abs ( this . treeDepth ( this . root . left ) - this . treeDepth ( this . root . right ) ) > 1 ) { return false ; } return true ; } public levelTraversal ( root ) { if ( ! root ) return [ ] ; let result = [ ] , queue = [ root ] ; while ( queue . length ) { let levelSize = queue . length ; let currentLevel = [ ] ; while ( levelSize -- ) { let node = queue . shift ( ) ; currentLevel . push ( node . val ) ; if ( node . left && node . left . val !== null ) queue . push ( node . left ) ; if ( node . right && node . right . val !== null ) queue . push ( node . right ) ; } result . push ( currentLevel ) ; } return result ; } } export default Tree ; export { TreeNode } ;