How to check the balance of binary trees by LeetCode

This article mainly shows you "LeetCode how to check the balance of binary trees". The content is simple and easy to understand, and the organization is clear. I hope it can help you solve your doubts. Let Xiaobian lead you to study and learn this article "LeetCode how to check the balance of binary trees".

1. Brief description of the problem

Implement a function to check whether the binary tree is balanced.

In this case, the balanced tree is defined as follows:

The height difference between two subtrees of any node does not exceed 1.

2, example

Example 1: Given binary tree [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 returns true. Example 2: Given binary tree [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \4 4 returns false.

3, the solution to the problem

solve recursively

4, the solution program

public class IsBalancedTest { public static void main(String[] args) { TreeNode t1 = new TreeNode(3); TreeNode t2 = new TreeNode(9); TreeNode t3 = new TreeNode(20); TreeNode t4 = new TreeNode(15); TreeNode t5 = new TreeNode(7); t1.left = t2; t1.right = t3; t3.left = t4; t3.right = t5; boolean balanced = isBalanced(t1); System.out.println("balanced = " + balanced);

}

public static boolean isBalanced(TreeNode root) { if (root == null) { return true; } int leftDepth = dfs(root.left); int rightDepth = dfs(root.right); int abs = Math.abs(leftDepth - rightDepth); if (abs