The title

LeetCode 110, balanced binary tree association type: tree

Given a binary tree, determine whether it is a highly balanced binary tree. In this case, a highly balanced binary tree is defined as: the absolute value of the height difference between the left and right subtrees of each node of a binary tree is no more than 1. Example 1:Copy the code

Input: root = [3,9,20,null,null,15,7] output: trueCopy the code

Input: root = [1,2,2,3,3,null,null,4,4Copy the code

Time to solve the problem.

class Solution {
    public boolean isBalanced(TreeNode root) {
     
     
 
       
    }
}
Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. This problem uses a top-down recursion to determine whether it is a balanced binary tree
  2. At each root node, the maximum depth difference between the left and right subtrees is judged to be no more than one, then continue
  3. Otherwise return false

Answers to analysis

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Answer successful: Execution time :1 ms, beat 99.98% of Java users memory consumption :38.4 MB, beat 78.22% of Java users

Class Solution {public Boolean isBalanced(TreeNode root) {if (root == null) {return true; } else { int leftDep = dep(root.left); Int rightDep = dep(root.right); If (math.abs (leftdep-rightdep)<=1) {return isBalanced(root.left) && from top to bottom isBalanced(root.right); } else { return false; }}} public int dep(TreeNode node) {if (node == null) {return 0; } else { int leftDep = dep(node.left) + 1; int rightDep = dep(node.right) + 1; return Math.max(leftDep, rightDep); }}}Copy the code