leetcode110 -- 平衡二叉树Java

leetcode110 -- 平衡二叉树Java

题目描述：

思路：

• 一般的思路：遍历二叉树，对二叉树的每一个节点计算左右的最大高度，但是计算一颗二叉树的最大深度也需要递归遍历这棵树的所有节点，如果对每个节点都计算一遍最大深度，时间复杂度会比较高。
• 比较好的思路：反过来思考，只计算一次最大深度，计算的过程中顺便判断二叉树是否平衡：对于每个节点，先计算出来左右子树的最大高度，然后在后序遍历的位置根据左右子树的最大高度判断平衡性即可。

代码实现：

 // 思路：只是计算一次最大深度，计算的过程中顺便判断二叉树是否平衡
 // 对于每一个节点，先计算出左右子树的最大高度，然后在后续遍历的位置根据左右子树的最大高度判断平衡性
class Solution {
    public boolean isBalanced(TreeNode root) {
        maxDepth(root);
        return isBalanced;

    }
    // 一般时候都要设置一个变量来进行记录
    boolean isBalanced = true;
    // 设置一个函数，输入一个节点，返回以该节点为根的二叉树的最大深度
    int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        // if (!isBalanced){
        //     // 随便返回一个值返回即可，旨在结束递归
        //     return -666
        // }
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);

        // 左右根，后序遍历的位置
        // 如果左右最大深度大于1，就不是平衡二叉树
        if (Math.abs(rightMaxDepth - leftMaxDepth) > 1){
            isBalanced = false;
        }
        // 其实只是返回以该节点为根的二叉树的最大深度
        return 1 + Math.max(leftMaxDepth, rightMaxDepth);
    }
}