Algorithm Interview Replay: Balancing binary trees (bytes)

In the previous series, we learned about binary tree depth and DFS. If not, check out the previous article. And today we’re going to apply that, and we’re going to go straight to the problem.

01. Topic analysis

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:

Given a binary tree [3,9,20, NULL, NULL,15,7] 3 / \ 9 20 / \ 15 7 returnstrue 。
Copy the code

Example 2:

Given a binary tree [1,2,2,3,3, NULL, NULL,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 returnsfalse 。
Copy the code

02. Graphical analysis

We want to determine whether a tree satisfies a balanced binary tree. We want to determine whether the two children of the current node satisfy a balanced binary tree, and whether the height difference between the two children is greater than 1. So as long as we can get the height and make a judgment based on the height.

Let’s review our previous solution for tree height:

The only thing to note here is that if we decide that any of these nodes does not satisfy a balanced binary tree, then the whole tree is no longer a balanced binary tree, and we can block it, so we don’t have to keep recursing.

Also, note that the following tree is not a balanced binary tree:

03. Code analysis

According to the analysis, the logic is very clear and the code is obtained smoothly:

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if! isBalanced(root.Left) || ! isBalanced(root.Right) {return false
    }
    leftH := maxDepth(root.Left) + 1;     
    rightH := maxDepth(root.Right) + 1;   
    if abs(leftH-rightH) > 1 {
        return false
    }
    return true
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left),maxDepth(root.Right)) + 1
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a 
}
Copy the code

Execution Result:

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download