Leetcode110 -- balanced binary tree Java

Title Description ：

Ideas ：

• General idea ： Traversing the binary tree , Calculate the maximum height of each node of the binary tree , But calculating the maximum depth of a binary tree also requires recursive traversal of all nodes of the tree , If the maximum depth is calculated for each node , Time complexity will be higher .
• A better idea ： Think in reverse , Calculate the maximum depth only once , In the process of calculation, judge whether the binary tree is balanced ： For each node , First calculate the maximum height of the left and right subtrees , Then judge the balance according to the maximum height of the left and right subtrees at the post order traversal position .

Code implementation ：

/** * 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; * } * } */
 //  Ideas ： Just calculate the maximum depth once , In the process of calculation, judge whether the binary tree is balanced 
 //  For each node , First calculate the maximum height of the left and right subtrees , Then judge the balance according to the maximum height of the left and right subtrees at the position of subsequent traversal 
class Solution {
    
    public boolean isBalanced(TreeNode root) {
    
        maxDepth(root);
        return isBalanced;

    }
    //  Generally, a variable should be set to record 
    boolean isBalanced = true;
    //  Set up a function , Enter a node , Returns the maximum depth of the binary tree with this node as its root 
    int maxDepth(TreeNode root){
    
        if (root == null){
    
            return 0;
        }
        // if (!isBalanced){
    
        // //  Just return any value , Designed to end recursion 
        // return -666
        // }
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);

        //  Left and right , Postorder traversal position 
        //  If the maximum left and right depth is greater than 1, It's not a balanced binary tree 
        if (Math.abs(rightMaxDepth - leftMaxDepth) > 1){
    
            isBalanced = false;
        }
        //  In fact, it just returns the maximum depth of the binary tree with this node as the root 
        return 1 + Math.max(leftMaxDepth, rightMaxDepth);
    }
}