平衡二叉树

未匹配的标注

题目描述

输入一棵二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树

分析

平衡树(Balance Tree,BT) 指的是:任意节点的左右子树的高度差都小于等于1。
二叉树的深度所用的后序遍历解法一样,只不过增加了对每个节点的左右子树高度差是否小于等于1的判断,如果高度差大于1,则直接返回 -1(false)。

代码


<?php

namespace app\index\controller;

class Test 
{

   /**
    * 构建二叉树测试数据
    */
    public function test()
    {
        $pRoot = new TreeNode(1);
        $node1 = new TreeNode(2);
        $node2 = new TreeNode(3);
        $pRoot->right = $node1;
        $node1->right = $node2;

        $this->IsBalanced_Solution($pRoot);  // 调用
    }

    /**
     * 如果递归后返回 -1,则不是平衡二叉树(false)
     */
    function IsBalanced_Solution($pRoot)
    {
        return $this->recursive($pRoot) != -1;
    }

    /**
     * 后序遍历,递归,计算左右子树高度差
     */
    function recursive($pRoot)
    {
        if ($pRoot == NULL) return 0;             // 终止递归条件:越过叶子节点

        $left = $this->recursive($pRoot->left);   // 递归左子树
        if ($left == -1) return -1;               // 如果不平衡,直接返回 -1

        $right = $this->recursive($pRoot->right); // 递归右子树
        if ($right == -1) return -1;              // 如果不平衡,直接返回 -1

        // 如果左右子树高度差符合平衡树要求,则返回树的深度,否则返回 -1
        return abs($left - $right) < 2 ? max($left, $right) + 1 : -1;
    }
}

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 查看所有版本


暂无话题~