`
淡淡的一抹
  • 浏览: 18753 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Balanced Binary Tree

 
阅读更多
题目描述
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

解题思路
是一个关于二叉树的基本题,判断一颗树是否是平衡二叉树。

相关知识
(1)平衡二叉树的概念
平衡二叉树(Balanced Binary Tree),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

自己的代码
package leetcode;

/*public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}*/

public class BalancedBinaryTree {
	public boolean isBalanced(TreeNode root) {
		//空树处理
		if(root == null) return true;
		
		boolean balanced = true, leftIsBalanced, rightIsBalanced;
		int leftHight, rightHight;
		//左子树处理
		if(root.left == null) {
			leftHight = 0;
			leftIsBalanced = true;
		}
		else {
			leftIsBalanced = isBalanced(root.left);
			leftHight = root.left.val;
		}
		//右子树处理
		if(root.right == null) {
			rightHight = 0;
			rightIsBalanced = true;
		}
		else {
			rightIsBalanced = isBalanced(root.right);
			rightHight = root.right.val;
		}
		//本节点处理
		if(leftHight > rightHight) {
			root.val = leftHight + 1;
			if(leftHight-rightHight>1) balanced = false;
		}
		else {
			root.val = rightHight + 1;
			if(rightHight-leftHight>1) balanced = false;
		}
		
        return leftIsBalanced && rightIsBalanced && balanced;
    }
	
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(1);
		TreeNode node2 = new TreeNode(2);
		TreeNode node3 = new TreeNode(3);
		TreeNode node4 = new TreeNode(4);
		TreeNode node5 = new TreeNode(5);
		TreeNode node6 = new TreeNode(6);
		
		/*node1.left = node2;
		node1.right = node3;
		node2.left = node4;
		node2.right = node5;
		node4.right = node6;*/
		
		/*node1 = null;*/
		
		node1.left = node2;
		
		BalancedBinaryTree bbt = new BalancedBinaryTree();
		boolean result = bbt.isBalanced(node1);
		System.out.println(result);
	}
}
分享到:
评论

相关推荐

    leetcode的题目:Balanced Binary Tree

    leetcode的题目:Balanced Binary Tree

    Balanced-binary-tree.rar_Balanced Binary Tree

    手动输入数据,加入到二叉树中,并生成平衡二叉树,对学习C++及数据结构有较大帮助

    cpp-算法精粹

    Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from...

    二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造 课设作业 完整代码

    平衡二叉树(Balanced Binary Tree)又被称为AVL树。具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的: 二叉排序树的实现...

    c语言平衡二叉树代码示例

    平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),它具有以下性质: 1. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。 2. 左右两个子树都是一棵平衡二叉树。 平衡二叉树大部分操作和...

    平衡二叉树的所有操作(全)

    平衡二叉树(Balanced Binary Tree),简称平衡树(AVL树):树上任一结点的左子树和右子树的高度之差不超过1。平衡二叉树的一系列操作:删除、插入(在二叉排序树中插入新结点后,如何保持平衡)、调整平衡等等等。...

    左程云leetcode-algorithm-and-data-structure:算法+数据结构=程序

    树(Balanced Binary Tree/AVL Tree) 红黑树(Red-Black Tree) 伸展树(Splay Tree) B-树(B-Tree) 线索二叉树(Threaded Binary Tree) 前缀树/字典树(Trie) 5. 哈希/散列(Hashing) 哈希表(Hash Table) ...

    左程云leetcode-algorithm-and-data-structure:算法+数据结构=程序https://en.wikipedia

    树(Balanced Binary Tree/AVL Tree) 红黑树(Red-Black Tree) 伸展树(Splay Tree) B-树(B-Tree) 线索二叉树(Threaded Binary Tree) 前缀树/字典树(Trie) 5. 哈希/散列(Hashing) 哈希表(Hash Table) ...

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    平衡二叉树算法详细解释

    形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。

    map-for-c-by-balanced-binary-tree

    基于平衡二叉树的C语言MAP,可以根据用户传入的类型自定义KEY和VAL的类型,如int or 结构体

    LintCode:针对LintCode问题的Java解决方案

    [Balanced Binary Tree.java]( Binary Tree.java) Java 7 [最佳买卖股票I.java]( 最佳买卖股票I.java) Java 8 [最佳买卖股票II.java]( 最佳买卖股票II.java) Java 9 [最佳买卖股票III.jav

    leetcode和oj-interviewprep:面试准备

    balanced binary tree, red/black tree splay tree AVL tree Implementation 图表 There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list) B

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码写的很飘逸,果然是有LISP内功的人!...Balanced Binary Tree Binar

    Balanced-Binary-Tree.zip_site:www.pudn.com

    基本实现平衡二叉树的创建,插入和删除操作。使用C++代码实现

    AVLTree.rar_数据结构_Visual_C++_

    数据结构,平衡二叉树平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。...

    binary_trees

    二叉树 学习目标 What is a binary tree What is the difference between a binary tree and a Binary ...What is a complete, a full, a perfect, a balanced binary tree 数据结构 基本二叉树 /** * struct binary

    平衡二叉树详解及java代码的实现

    平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树(递归定义)的二叉排序树。...

    二叉排序树与平衡二叉树的实现

    ①平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高度大致相同。 ②任一结点的左右子树的高度均相同(如满二叉树),则二叉树是完全平衡的。通常,只要二叉树的高度为O(1gn),就可看作是平衡的。 ...

Global site tag (gtag.js) - Google Analytics