1. DFS

如果一个节点的左右子节点都是平衡的，并且左右子节点的深度差不超过 1，则可以确定这个节点就是一颗平衡二叉树。

  1. public class Solution {
  2.     public boolean IsBalanced_Solution(TreeNode root) {
  3.         if (root == null) return true;
  4.         //判断左子树和右子树是否符合规则，且深度不能超过2
  5.         return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right) && Math.abs(deep(root.left) - deep(root.right)) < 2;
  6.     }
  7.     //判断二叉树深度
  8.     public int deep(TreeNode root) {
  9.         if (root == null) return 0;
  10.         return Math.max(deep(root.left), deep(root.right)) + 1;
  11.     }
  12. }

2. 回溯

对于父节点，需要确定两个子节点深度之差小于一。对于作为子节点的立场，需要向自己的上一级节点传递的自己深度。

  1. public class Solution {
  2.     public boolean IsBalanced_Solution(TreeNode root) {
  3.         if(deep(root)==-1) return false;
  4.         return true;   
  5.     }
  6.     public int deep(TreeNode node){
  7.         if(node == null) return 0;
  8.         int left = deep(node.left);
  9.         if(left == -1 ) return -1;
  10.         int right = deep(node.right);
  11.         if(right == -1 ) return -1;
  13.         //两个子节点深度之差小于一
  14.         if((left-right) > 1 || (right-left) > 1){
  15.             return -1;
  16.         }
  17.         //父节点需要向自己的父节点报告自己的深度
  18.         return (left > right ? left:right) + 1;
  19.     }
  20. }