【DFS】检查二叉树平衡性

mario 2020年09月23日 140次浏览

前言

决定按标签做题,从dfs开始。

分析题目

image.png

解法

class Solution {
    private boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return flag;
    }
    //计算二叉树深度
    private int dfs(TreeNode n){
        if(n == null || !flag)
            return 0;
        int leftDepth = dfs(n.left)+1;
        int rightDepth = dfs(n.right)+1;
        if(Math.abs(leftDepth-rightDepth) > 1)
            flag = false;
        return Math.max(leftDepth,rightDepth);
    }
}