一、题目内容

image.png

二、题解

解法1：

思路

先序遍历，递归求当前子树的左子树与右子树深度差小于2

代码

  1. class Solution {
  2.     public boolean isBalanced(TreeNode root) {
  3.         if(root == null){
  4.             return true;
  5.         }
  6.         return Math.abs(depth(root.left)-depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
  7.     }
  9.     //求当前子树深度
  10.     public int depth(TreeNode root){
  11.         if(root == null){
  12.             return 0;
  13.         }
  14.         return Math.max(depth(root.left),depth(root.right))+1;
  15.     }
  16. }

解法2：

思路

后续遍历+剪枝，递归求当前子树的左子树与右子树深度差小于2，如果非平衡，直接返回结果false

代码

public class Solution_2 {

    /**
     * 判断非-1
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    public int recur(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = recur(root.left);
        if (left == -1) {
            return -1;
        }
        int right = recur(root.right);
        if (right == -1) {
            return -1;
        }
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}