Topic describes

Implement a function to check whether the binary tree is balanced. In this problem, a balanced tree is defined as follows: for any node, the height difference between the two subtrees is not more than 1. Example 1: Given a binary tree [3,9,20, NULL, NULL,15,7] 3 / \ 9 20 / \ 15 7 returns true. Example 2: Given a binary tree [1,2,2,3,3, NULL, NULL,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 returns false. Example 3: The following binary tree is balanced with node 3, but the left subtree 9 is unbalanced; 3 / \ 9 20 / / \ 4 15 7 / \ 10 8 Returns false. Source: LeetCode Link: https://leetcode-cn.com/problems/check-balance-lcci Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Their thinking

  • According to the definition of balance, the left and right subtree heights of each node are calculated.
    • If the height difference between the left and right subtrees of a node is greater than 1, it is unbalanced and false is returned, the algorithm ends.
    • Otherwise, the subtree rooted in the current node is balanced. Continue to check the balance of the left and right subtrees of the current node.

Computing the height of binary trees: recursion, decomposition problem;

  • Current binary tree height = Max (left subtree height, right subtree height) + 1
  • The left subtree height is calculated in the same way as in step 1
  • If the current node is null, 0 is returned as a recursive exit

The recursive exit can be reached by following the above decomposition method

code


/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */

function isBalanced(root: TreeNode | null) :boolean {
  if(root==null) {return true;
  }
  let leftTreeDepth:number=treeDepth(root.left); 
  let rightTreeDepth:number=treeDepth(root.right);
  if(Math.abs(leftTreeDepth-rightTreeDepth)>1) {return false;
  }
  // If the current tree node is balanced, check the balance of the left and right subtrees;
  return isBalanced(root.left)&&isBalanced(root.right);

};

// Calculate the height of the tree;
 function treeDepth(root: TreeNode | null) :number{
     if(root==null) {return 0;
     }
     
     return Math.max(treeDepth(root.left),treeDepth(root.right))+1;

 }
Copy the code

A review of binary trees

【 Review old and learn new 】101. Symmetric binary treesUsing queue, recursive realization of binary tree judgment

【 Review old and learn new 】102. Sequence traversal of binary treesBreadth-first traversal, queue first in, first out principle

【 Review old and learn new 】104. Maximum depth of a binary treeBreadth-first traversal, recursive implementation

【 Review old and learn new 】1367. Lists in binary treesRecursive decomposition problem solving

Flip binary tree breadth-first, depth-first, fore-order, back-order recursion 4 solutions Binary tree expansion is the depth – first and pre-order traversal feature of linked list