[LeetCode Hot 100] LeetCode110. 平衡二叉树

题目描述

思路

LeetCode104. 二叉树的最大深度 变种

方法一：后序遍历(递归、dfs)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private boolean isbalancedTree = true;
    public boolean isBalanced(TreeNode root) {
        depth(root);
        return isbalancedTree;
    }
    // 求当前节点的高度
    private int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        if (Math.abs(left - right) > 1) isbalancedTree = false;
        return Math.max(left, right) + 1; 
    }
}