// 二叉树的生成 function NodeTree(value) { this.value = value; this.left = null; this.right = null; } let ta = new NodeTree('a'); let tb = new NodeTree('b'); let tc = new NodeTree('c'); let td = new NodeTree('d'); let te = new NodeTree('e'); let tf = new NodeTree('f'); let tg = new NodeTree('g'); ta.left = tb; ta.right = tc; tb.left = td; tb.right = te; tc.left = tf; tc.right = tg; 如上面的数据结构,ta是一颗满二叉树,也是一颗平衡二叉树, 平衡二叉树的定义是啥呢? 条件一:它必须是二叉查找树(二叉搜索树)。 条件二:每个节点的左子树和右子树的高度差至多为1 // 获取一颗二叉树的深度 function getDeep(doubleTree) { if (doubleTree.value === null) return 0; let left = 0, right = 0; if (doubleTree.left) left = getDeep(doubleTree.left) if (doubleTree.right) right = getDeep(doubleTree.right); return Math.max(left, right) + 1; } /** * 判断一棵树是否为平衡二叉树 * 1.条件, 二叉树里面的左右子树相差不能超过1 * 2. */ function balanceTree(doubleTree){ // 如果传入的数据,为空,则平衡 if (!doubleTree|| doubleTree === '') return true; let leftNum = 0, rightNum = 0; if (doubleTree.left) { leftNum = getDeep(doubleTree.left); } if (doubleTree.right){ rightNum = getDeep(doubleTree.right); } if (Math.abs(leftNum - rightNum) <= 1){ return balanceTree(doubleTree.left) && balanceTree(doubleTree.right) }else { // 大于1,改二叉树不平衡 return false; } } console.log(balanceTree(ta)) // 结果是true 那我们来一颗非平衡的二叉树,如下: let ba = new Node('ba'); let bb = new Node('bb'); let bc = new Node('bc'); let bd = new Node('bd'); let be = new Node('be'); let bf = new Node('bf'); ba.left = bb; ba.right = bc; bb.left = bd; bd.right = be; be.left = bf; console.log(balanceTree(ba)) // 结果是false