Leetcode之(110. Balanced Binary Tree)

Leetcode · curry · 于 2个月前 发布 · 100 次阅读

题目描述

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

题目案例

    3
   / \
  9  20
     /  \
    15   7

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

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

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

题目分析

如果是空树的话,那么是正确的,否则递归他的左右子树进行比较,最后用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;
}

本文由 curry 创作,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

共收到 1 条回复 二叉树 php 算法
1楼 已删除.
添加回复 (需要登录)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册
吴亲库里的深夜食堂