输入一棵二叉树，判断该二叉树是否是平衡二叉树。 https://leetcode-cn.com/problems/balanced-binary-tree/ ``` /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function IsBalanced_Solution(pRoot) { // write code here if(pRoot==null){return true;} var left = TreeDepth(pRoot.left); var right = TreeDepth(pRoot.right); var dif = Math.abs(left-right); if(dif>1){return false;} return IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right); } // 二叉树的深度 function TreeDepth(root){ if(!root || root.length==0){return 0;} var left = TreeDepth(root.left); var right = TreeDepth(root.right); return Math.max(left,right)+1; } ``` ``` 1. 比较两颗子树的高度，两边都取最大深度 2. 查看两颗子树高度差是否相差为1 3. 如果大于1，那么将其标记为-1（表示不是AVL树），然后每次递归时先判断该节点的子树是否时AVL树 function IsBalanced_Solution(pRoot) { return orderTree(pRoot) !== -1; } function orderTree(root) { if(!root) return 0; let left = orderTree(root.left); let right = orderTree(root.right); if(left === -1 || right === -1 || Math.abs(left-right) > 1) return -1; return Math.max(left,right)+1; } ```