[leetcode] balanced binary tree

#LeetCode A daily topic 【 Special topic of binary tree 】

• Balanced binary trees
  https://leetcode-cn.com/problems/balanced-binary-tree/
• analysis
  The definition of balanced binary tree ：
  The absolute value of the height difference between the left and right subtrees of each node does not exceed 1, That is to say, both the left and right subtrees of a balanced binary tree are balanced binary trees , And the absolute value of the height difference between the left and right subtrees does not exceed 1;
  When finding the height of a tree , Use dfs Recursion , Knowing the height of the left and right subtrees can also determine whether the tree is balanced , If a subtree is unbalanced , Then the whole tree is unbalanced .
• Realization

public boolean isBalanced(TreeNode root) {
    
        //  It's not equal to -1, Namely balance （ And the return value is the height of the tree ）
        return height(root) != -1;
    }

    //  Since this method returns the height of the tree , At the same time, it can also judge whether the tree is a balanced binary tree 
    //  Be flexible , When the tree is unbalanced, it returns directly to -1（ That is, the height difference >1）, One of the word trees is unbalanced , The tree must be unbalanced 
    private int height(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }
        int left = heightOptimize(root.left);
        int right = heightOptimize(root.right);

        //  One of the trees is unbalanced , Return -1, out-off-balance 
        if (left == -1 || right == -1) {
    
            return -1;
        }
        //  The height difference is greater than 1, out-off-balance 
        if (Math.abs(left - right) > 1) {
    
            return -1;
        }
        //  normal , Balance returns to its height 
        return Math.max(left, right) + 1;
    }

LeetCode Time consuming ：0ms

• summary

When finding the height of a tree , Use dfs Recursion , Knowing the height of the left and right subtrees can also determine whether the tree is balanced , If a subtree is unbalanced , Then the whole tree is unbalanced