LeetCode刷题【剑指 Offer 55 – II】平衡二叉树

    3
   / \
  9  20
    /  \
   15   7

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

DFS深搜模板套用

解题思路

1. 借助深搜模板，计算每层对应高度
2. 判断每个节点的左右子节点高度相差是否小于2
3. 如果不小于2则不是平衡二叉树

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    boolean isBalanced = true;
    public boolean isBalanced(TreeNode root) {
        dfs(root,0);
        return isBalanced;
    }

    public int dfs(TreeNode node, int dep){
        if (!isBalanced || null == node){
            return dep;
        }
        dep++;
        int leftDep = dfs(node.left,dep);
        int rightDep = dfs(node.right,dep);
        if (Math.abs(leftDep-rightDep )< 2){
            return Math.max(leftDep,rightDep);
        }
        isBalanced = false;
        return Math.max(leftDep,rightDep);
    }
}