关键词:
题目
平衡二叉树的性质为:要么是一颗空树,要么任何一个节点的左右子树高度差的绝对值不超过1。给定一棵二叉树的头结点head,判断这棵二叉树是否为平衡二叉树。
难度:??
基础理解
以下是个人认为对概念叙述较为详细的参考链接:
- 对平衡二叉树的理解:判断二叉树是否为平衡二叉树
- 对先序、中序、后序遍历的理解:二叉树的实现及先序、中序、后序遍历
设计
概要设计
- 设计一个初始树节点模型
- 接收节点变量并判断是否为平衡二叉树的方法
- 如何判断是否为平衡二叉树
- 包含对左右各分支节点的计数器,并以此相减,是否满足绝对值 <=1 的判断方法
- 假若左分支的左节点或右节点不满足平衡二叉树,直接退出遍历过程
- 能改变假定 boolean 变量值的存储结构——数组
详细设计
初始树节点模型
class Node
int value;
Node left;
Node right;
Node(int value)
this.value = value;
布尔的判断,假定一个布尔首索引值true,通过判断平衡二叉树的具体方法将决定假定布尔值是否改变,调用该方法后,并返回布尔数组的首索引值。
public boolean isBalance(Node node)
boolean[] booleans = new boolean[1];
booleans[0] = true;
getHeight(node, 0, booleans);
return booleans[0];
判断是否为平衡二叉树的具体方法
- 利用自身的回调完成对节点遍历,闭包将返回值传递給变量
- 如果(节点)左分支计数 l 减去右分支计数 r 绝对值大于1,则将数组首索引假定布尔值改变
- 此方法的判断true或false时,所返回的整型值是多少并不重要,重要的是能否影响到假定的布尔值,这将决定整个二叉树是否为平衡二叉树
public int getHeight(Node node, int level, boolean[] booleans)
if (head == null)
return level;
int l = getHeight(node.left, level + 1, booleans);
int r = getHeight(node.right, level + 1, booleans);
if (Math.abs(l - r) > 1)
booleans[0] = false;
return Math.max(l, r);
实现
import org.junit.Test;
/**
* @author lorem
*/
public class BalanceTreeGoTest
class Node
int value;
Node left;
Node right;
Node(int value)
this.value = value;
public boolean isBalance(Node node)
boolean[] booleans = new boolean[1];
booleans[0] = true;
getHeight(node, 0, booleans);
return booleans[0];
public int getHeight(Node node, int level, boolean[] booleans)
if (node == null)
return level;
int l = getHeight(node.left, level + 1, booleans);
int r = getHeight(node.right, level + 1, booleans);
if (Math.abs(l - r) > 1)
booleans[0] = false;
return Math.max(l, r);
@Test
public void test()
Node node = new Node(1);
node.left = new Node(2);
node.right = new Node(3);
node.left.left = new Node(4);
node.left.left.left = new Node(5);
System.out.println(isBalance(node));
模拟过程
以此类二叉树为例,并结合代码演示推导过程
左分支推导同理
剑指offer--平衡二叉树(代码片段)
题目输入一棵二叉树,判断该二叉树是否是平衡二叉树。思路递归判断,先判断自身左右子树高度差,再递归判断左右子树是否为平衡二叉树;packagesolution;publicclassSolution28publicbooleanIsBalanced_Solution(TreeNoderoot)if(root==null)//递归出口... 查看详情
判断二叉树是否为平衡二叉树(代码片段)
问题:判断二叉树是否为平衡二叉树面试题55-II.平衡二叉树(从底至顶、从顶至底,清晰图解)-平衡二叉树-力扣(LeetCode)方法一:后序遍历+剪枝,自下而上后续遍历节点,递归向上返回子树的深度,同时判断当前子树是否为... 查看详情
剑指offer:平衡二叉树(代码片段)
题目描述:输入一棵二叉树,判断该二叉树是否是平衡二叉树。 思路分析:首先要明确平衡二叉树的定义。平衡二叉是左右子树的高度差小于等于1,且左右子树都为平衡二叉树。这里就存在一个递归判断左右子树是否为平... 查看详情
二叉树12:判断平衡二叉树(代码片段)
LeetCode110 给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 首先我们注意到这里提到的是高度,前面我们还... 查看详情
平衡二叉树实例--判断输入后序序列是否为平衡二叉树(代码片段)
1boolverifyPostorder(vector<int>&postorder)2if(postorder.empty())returntrue;3boolres=helper(postorder,0,postorder.sizee()-1);4returnres;567boolhelper(vector<int>&postorder,intsta 查看详情
判断是否是平衡二叉树(代码片段)
classSolutionpublic:intheight(TreeNode*root)//求当前结点高度if(root==NULL)return0;elsereturnmax(height(root->left),height(root->right))+1;boolisBalanced(TreeNode*root)if(root== 查看详情
剑指offer-平衡二叉树(代码片段)
packageTree;/***平衡二叉树*输入一棵二叉树,判断该二叉树是否是平衡二叉树。*平衡二叉树(BalancedBinaryTree)又被称为AVL树(有别于AVL算法),且具有以下性质:*它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且... 查看详情
面试题:平衡二叉树(代码片段)
题目描述:输入一棵二叉树,判断该二叉树是否是平衡二叉树。思路:利用上一题求二叉树的深度publicclassSolutionpublicbooleanIsBalanced_Solution(TreeNoderoot)if(root==null)returntrue;intleft=depth(root.left);intright=depth(root.right);intbalance=le 查看详情
leetcode刷题python110.平衡二叉树(代码片段)
1题目给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。2解析高度的函数,即可判断二叉树是否平衡。具体... 查看详情
平衡二叉树的判断(代码片段)
平衡二叉树的判断如何判断是否为平衡二叉树?答:每个节点的左右子树高度差的绝对值小于等于1,我们认为该二叉树平衡;?只要有一个节点的左右子树高度差绝对值大于1,我们认为这颗二叉树不平衡。因此,判断一棵树是否... 查看详情
newcode-平衡二叉树(代码片段)
题目描述输入一棵二叉树,判断该二叉树是否是平衡二叉树。解析“平衡二叉树(BalancedBinaryTree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。自己提... 查看详情
平衡二叉树判断
...17/article/details/70960005 有一棵二叉树,请设计一个算法判断这棵二叉树是否为平衡二叉树。给定二叉树的根结点root,请返回一个bool值,代表这棵树是否为平衡二叉树。 import java.util.*; //判断一棵二叉树是否是... 查看详情
判断一个二叉树是否是平衡二叉树
题目:判断一个二叉排序树是否是平衡二叉树思路:利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树。1#include<stdio.h>2#include"stdafx.h"34structBinaryTreeNode5{6intm_nValue;7BinaryTreeNode*m_pLeft;8BinaryTreeNode*m_pRight;9};1011BinaryTre... 查看详情
java判断平衡二叉树(代码片段)
⭐算法入门⭐《二叉树-平衡二叉树》简单01——leetcode110.平衡二叉树(代码片段)
...加群须知一、题目1、题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 样例输入:root=... 查看详情
二叉树小结(代码片段)
...二叉树的遍历递归遍历非递归遍历层序遍历二叉树的翻转判断二叉树是否对称二叉树的最大深度二叉树的最小深度求二叉树的总结点数判断是否是平衡二叉树BFS模板二叉树的遍历递归遍历voidpre(TreeNode*p)if(p!=NULL)vect.push_back(p->... 查看详情
110.平衡二叉树-前序遍历-简单(代码片段)
问题描述给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树[3,9,20,null,null,15,7]3/920/157返回true。示例2:... 查看详情
数据结构与算法二叉树——平衡二叉树(代码片段)
...衡二叉树LeetCode:平衡二叉题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。示例:给定二叉树[3,9,20,null,null,15,7]3/920/157返回true思想:使用实例域变量记录是否与有不满足平衡的节点出现,使用一次递归即可。代码/... 查看详情