This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the fifth day of my August more article, today to bring you about binary tree algorithm is called balanced binary tree, the text is as follows.

Topic:

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 does not exceed 1.

Their thinking

A wave concept is emphasized here:

  • Binary tree node depth: refers to the number of the longest simple path edges from the root node to the node
  • The height of a binary tree node: the number of the longest simple path edges from the node to the leaf node

When we find the height of a binary tree, we can use a bottom-up recursion, and the bottom-up recursion is similar to a post-order traversal.

Recursive analysis:

  1. Specify parameters and return values for recursive functions

The parameter is the incoming node, and the return value is the depth of the tree where the incoming node is the root node. So how do we mark whether the left and right subtrees are more than one apart. It makes no sense to return the height if the root tree is no longer a balanced tree. So if it is no longer a binary balanced tree, you can return -1 to indicate that it is no longer a binary balanced tree.

  1. Explicit termination conditions

Return 0, indicating that the current node is the height of the root node is 0

  1. Explicit logic for single-layer recursion

How to determine whether a binary tree with root node is balanced? Of course, it is the difference between the height of the left subtree and the height of the right subtree.

If the difference is less than or equal to 1, return the height of the current binary tree. Otherwise, return -1, indicating that it is no longer a binary tree.

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; *} *} */
class Solution {
    // // recursion from bottom to top
    // public boolean isBalanced(TreeNode root) {
    // return height(root) >= 0;
    // }

    // public int height(TreeNode root) {
    // if (root == null) return 0;
    // int leftHeight = height(root.left);
    // if (leftHeight == -1) return -1;

    // int rightHeight = height(root.right);
    // if (rightHeight == -1) return -1;

    // return Math.abs(leftHeight - rightHeight) > 1 ? -1 : Math.max(leftHeight, rightHeight) + 1;
    // }

    // A better way to understand
    private static final int UNBALANCED = -1;

    public boolean isBalanced(TreeNode root) {
        returnhelper(root) ! = UNBALANCED; }public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }

        If the left subtree is not a balanced binary tree, return to both
        int left = helper(root.left);
        if (left == UNBALANCED) {
            return UNBALANCED;
        } 

        If the right subtree is not a balanced binary tree, return to both
        int right = helper(root.right);
        if (right == UNBALANCED) {
            return UNBALANCED;
        }

        If the left and right subtrees are balanced binary trees, but their heights differ by more than one, return to both
        if (Math.abs(left - right) > 1) {
            return UNBALANCED;
        }

        // Otherwise return the maximum height of the nodes in the binary tree
        return Math.max(left, right) + 1; }}Copy the code

The last

Complexity analysis

Time complexity: O(n), where n is the number of nodes in the binary tree. Using bottom-up recursion, the height of each node is calculated and the balance is determined only once. In the worst case, all nodes in the binary tree need to be traversed, so the time complexity is O(n).

Space complexity: O(n), where n is the number of nodes in the binary tree. The spatial complexity depends primarily on the number of layers of recursive calls, which do not exceed n.