# Leetcode110 -- balanced binary tree Java

2022-01-27 01:30:03 Co-King

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);
}
}
``````