Byte interview question - judge whether a tree is a balanced binary tree

4. Judge a tree Is it Balanced binary trees （ Time complexity ：O(N^2)）

Original link

***** Never mind recursive logic , Just write the code according to the top root node

    //  Get the height of the binary tree   Time complexity ：O(N)
    int getHeight(TreeNode root) {
    
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight ?
                leftHeight+1 : rightHeight+1);
    }
    // Time complexity ：O(N^2)
    public boolean isBalanced(TreeNode root) {
    
        if(root == null) return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight-rightHeight) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

Optimize , When there is an imbalance , No more recursion , But in turn return -1

Thinking angle when optimizing , Is to think from the bottom up

    // This question   It's the original question that byte passed  O(n)
    public int maxDepth(TreeNode root) {
    
        if(root == null) return 0;
        int leftTree = maxDepth(root.left);
        int rightTree = maxDepth(root.right);

        if(leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree - rightTree) <= 1) {
    
            return Math.max(leftTree,rightTree) + 1;
        }else {
    
            return -1;
        }
    }

    public boolean isBalanced2(TreeNode root) {
    
        if(root == null) return true;
        return maxDepth(root) >= 0;
    }

***** Solve the mind

The original method is ： Root node Compare the height of the left and right subtrees ,
then Then judge the height difference of the subtrees of the left and right subtrees , This will recurse twice The time complexity is （O N²）

Modification method ： Is to traverse only once , When calculating the height of the tree , Determine whether it is a balanced binary tree , If not , Then stop calculating That is O（N）