- 浏览: 18753 次
- 性别:
- 来自: 北京
文章分类
最新评论
题目描述
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,并且左右两个子树都是一棵平衡二叉树。
自己的代码
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); } }
发表评论
-
Java中String与StringBuffer的区别
2014-10-29 21:07 294String和StringBuffer的区别,网上资料可以说 ... -
String to Integer (atoi)
2014-10-29 17:13 391题目描述 Implement atoi to convert ... -
Implement strStr()
2014-10-28 15:17 277题目描述 Implement strStr(). Retu ... -
Valid Palindrome
2014-10-23 10:32 413题目描述 Given a string, determine ... -
ZigZag Conversion
2014-10-22 19:51 336题目描述 The string "PAYPALIS ... -
Add Binary
2014-10-22 19:43 296题目描述 Given two binary strings, ... -
Longest Common Prefix
2014-10-22 19:44 323题目描述 Write a function to find t ... -
Count and Say
2014-10-22 19:44 340题目描述 The count-and-say sequence ... -
Valid Sudoku
2014-10-21 10:22 348题目描述 Determine if a Sudoku is v ... -
Valid Parentheses
2014-10-21 09:41 313题目描述 Given a string containing ... -
Palindrome Number
2014-10-21 09:41 341题目描述 Determine whether an integ ... -
Length of Last Word
2014-10-21 09:41 351题目描述 Given a string s consists ... -
Minimum Depth of Binary Tree
2014-10-21 09:41 302题目描述 Given a binary tree, find ... -
Remove Nth Node From End of List
2014-10-20 16:36 251题目描述 Given a linked list, remov ... -
Path Sum
2014-10-20 15:37 287题目描述 Given a binary tree and a ... -
Binary Tree Level Order Traversal II
2014-10-20 11:17 227题目描述 Given a binary tree, retur ... -
Binary Tree Level Order Traversal
2014-10-20 11:03 287题目描述 Given a binary tree, retur ... -
Pascal's Triangle II
2014-10-20 10:07 250题目描述 Given an index k, return t ... -
Pascal's Triangle
2014-10-19 12:24 309题目描述 Given numRows, generate th ... -
Plus One
2014-10-19 11:51 326题目描述 Given a non-negative numbe ...
相关推荐
leetcode的题目:Balanced Binary Tree
手动输入数据,加入到二叉树中,并生成平衡二叉树,对学习C++及数据结构有较大帮助
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...
平衡二叉树(Balanced Binary Tree)又被称为AVL树。具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的: 二叉排序树的实现...
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),它具有以下性质: 1. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。 2. 左右两个子树都是一棵平衡二叉树。 平衡二叉树大部分操作和...
平衡二叉树(Balanced Binary Tree),简称平衡树(AVL树):树上任一结点的左子树和右子树的高度之差不超过1。平衡二叉树的一系列操作:删除、插入(在二叉排序树中插入新结点后,如何保持平衡)、调整平衡等等等。...
树(Balanced Binary Tree/AVL Tree) 红黑树(Red-Black Tree) 伸展树(Splay Tree) B-树(B-Tree) 线索二叉树(Threaded Binary Tree) 前缀树/字典树(Trie) 5. 哈希/散列(Hashing) 哈希表(Hash Table) ...
树(Balanced Binary Tree/AVL Tree) 红黑树(Red-Black Tree) 伸展树(Splay Tree) B-树(B-Tree) 线索二叉树(Threaded Binary Tree) 前缀树/字典树(Trie) 5. 哈希/散列(Hashing) 哈希表(Hash Table) ...
* [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 分别为左、右子树的深度。
基于平衡二叉树的C语言MAP,可以根据用户传入的类型自定义KEY和VAL的类型,如int or 结构体
[Balanced Binary Tree.java]( Binary Tree.java) Java 7 [最佳买卖股票I.java]( 最佳买卖股票I.java) Java 8 [最佳买卖股票II.java]( 最佳买卖股票II.java) Java 9 [最佳买卖股票III.jav
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 Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码写的很飘逸,果然是有LISP内功的人!...Balanced Binary Tree Binar
基本实现平衡二叉树的创建,插入和删除操作。使用C++代码实现
数据结构,平衡二叉树平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。...
二叉树 学习目标 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
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树(递归定义)的二叉排序树。...
①平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高度大致相同。 ②任一结点的左右子树的高度均相同(如满二叉树),则二叉树是完全平衡的。通常,只要二叉树的高度为O(1gn),就可看作是平衡的。 ...