How to determine whether it is a balanced binary tree in PHP

In binary trees, there is one called balanced binary tree. Today we will introduce the method of judging whether the tree is a balanced binary tree. Friends in need can refer to it.

Given a binary tree, determine whether it is a highly balanced binary tree.

In this question, a height-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.

Example 1:

给定二叉树 [3,9,20,null,null,15,7]
   3
   / \
  9  20
    /  \
   15   7

Return true .

Example 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

Problem-solving ideas

The following is the most basic, top-to-bottom violent solution method. Each node may be a subtree, so you need to judge Whether it is a balanced binary tree. This method will produce a lot of repeated calculations and has high time complexity.

Bottom-up early blocking method: The idea is to perform a pre-order traversal of the binary tree, and return the maximum height of the subtree from bottom to top. If it is determined that a subtree is not a balanced tree, then "prun" it and go directly upward. return.

Top-down php code

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
    } 
* } 
*/
class Solution {
    /** * @param TreeNode $root * @return Boolean */
    function isBalanced($root) {
        if ($root == null) {
            return true;
        }
        if (abs($this->getHeight($root->left) - $this->getHeight($root->right)) > 1) {
            return false;
        }
        return $this->isBalanced($root->left) && $this->isBalanced($root->right);
    }
    function getHeight($node)
    {
        if($node == NULL)
            return 0;
        return 1 + max($this->getHeight($node->left), $this->getHeight($node->right));
    }}

Bottom-up PHP code:

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
    } 
* } 
*/
class Solution {
    /** * @param TreeNode $root * @return Boolean */
    function isBalanced($root) {
        return $this->helper($root) >= 0;
    }
    public function helper($root){
        if($root === null){
            return 0;
        }
        $l = $this->helper($root->left);
        $r = $this->helper($root->right);
        if($l === -1 || $r === -1 || abs($l - $r) > 1) return -1;
            return max($l, $r) +1;
    }}

Recommended learning: php video tutorial

The above is the detailed content of How to determine whether it is a balanced binary tree in PHP. For more information, please follow other related articles on the PHP Chinese website!