110.md

March 24, 2019 · View on GitHub

:pencil2:Leetcode基础刷题之(110. Balanced Binary Tree)

2019-03-05 吴亲库里 库里的深夜食堂

:pencil2:描述

给定一个二叉树，判断它是否是一棵平衡二叉树。平衡二叉树的定义是：每一节点的两个子树的高度相差不能超过1。

:pencil2:题目实例

    3
   / \
  9  20
    /  \
   15   7

** 上图中符合高度差不大于1的要求。**

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

上图中根节点1的左右子树的高度差已然超过1，所以它不是平衡二叉树。

:pencil2:题目分析

如果是空树的话，那么是正确的，否则递归他的左右子树进行比较，最后用return -1来表示不平衡，下面是具体php实现代码。

   /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isBalanced($root) {
        return $this->high($root) !==-1;
    }
    
    function high($root){
        if(!$root){
            return 0;
        }
        $left=$this->high($root->left);
        $right=$this->high($root->right);
     
        if($left==-1 ||$right==-1 || abs($left-$right)>1){
            return -1;
        }
            return max($left,$right)+1;
    }

联系

​