平衡二叉树的定义

    根节点的左子树与右子树的高度差不能超过1 这棵二叉树的每个子树的符合第一条

    图例
    image.png
    图中这个就可以称为平衡二叉树

    不是平衡二叉树的示意图如下
    image.png
    上图中 子节点b的左子树深度为2 右子树的深度为0 ，不满足条件不是一个平衡二叉树
    使用代码实现

    1. class Node {
    2.     constructor(value) {
    3.         this.value = value;
    4.         this.left = null;
    5.         this.right = null;
    6.     }
    7. }
    9. let a = new Node('a');
    10. let b = new Node('b');
    11. let c = new Node('c');
    12. let d = new Node('d');
    13. let e = new Node('e');
    14. let f = new Node('f');
    15. let g = new Node('g');
    16. let h = new Node('h');
    17. let i = new Node('i');
    19. a.left = b;
    20. b.left = d;
    21. d.left = h;
    22. e.left = i;
    23. c.left = f;
    24. a.right = c;
    25. c.right = g;
    26. b.right = e;
    28. /**
    29.  * 判断是否为平衡二叉树
    30.  * 平衡二叉的满足条件
    31.  * 根节点的左子树与右子树的高度差不能超过1
    32.  * 这棵二叉树的每个子树的符合第一条
    33.  * @param {*} root 节点
    34.  * @returns Boolean
    35.  */
    36. function isBalanceTree(root) {
    37.     if(!root) return true;
    38.     let letTree = getDeep(root.left)
    39.     let rightTree = getDeep(root.right)
    40.     if(Math.abs(letTree - rightTree) > 1) return false
    41.     else return isBalanceTree(root.left) && isBalanceTree(root.right);
    42. }
    43. /**
    44.  * 获取二叉树的深度
    45.  * @param {*} root 节点
    46.  * @returns Number 返回左右子树的最深的层数
    47.  */
    48. function getDeep(root) {
    49.     if(!root) return 0 ;
    50.     let leftTree = getDeep(root.left);
    51.     let rightTree = getDeep(root.right);
    52.     return Math.max(leftTree,rightTree) + 1;
    53. }
    54. let root =  isBalanceTree(a)
    55. console.log(root)