Leetcode-110-balanced binary tree

subject

Ideas

1. The idea is to traverse the binary tree first , Return to the maximum height of the subtree from the bottom to the top , If a subtree is not a balanced tree, then “ prune ” , Go straight up .
2. If the height difference between left and right ≥2 ： Then return to -1, representative This subtree is not a balanced tree , Then go back up It's all balanced trees Will return non -1 Value

Code

    public boolean isBalanced(TreeNode root) {
    
        return recur(root) != -1;
    }

    // The idea is to traverse the binary tree first , Return to the maximum height of the subtree from the bottom to the top , If a subtree is not a balanced tree, then  “ prune ” , Go straight up .
    private int recur(TreeNode root) {
    
        // Null pointer returns 0
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        // If the height difference between the left and right subtrees of the current node <2  This indicates that the current node is a balanced subtree 
        // Return to node root Is the maximum height of the subtree of the root node , That is node  root  The maximum height of the left and right subtrees plus  1
        // But if the height difference between the left and right ≥2 ： Then return to  -1, representative   This subtree is not a balanced tree , Then go back up   It's all balanced trees   Will return non -1 Value 
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }