/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if (root == null) return true; else { if (!isBalanced(root.left) || !isBalanced(root.right)) return false; else if (Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1) return true; else return false; } } public int getDepth(TreeNode root){ if (root == null) return 0; else return Math.max(getDepth(root.left), getDepth(root.right)) + 1; } }
小测试过了 大测试超时= = 哎。。。递归果然就是时间效率不高
想了一下发现是isBalanced中已经用isBalanced算过一次深度了 之后又算一次深度 囧
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ import java.util.HashMap; public class Solution { static HashMap<TreeNode, Integer> depths = new HashMap<TreeNode, Integer>(); public boolean isBalanced(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if (root == null) return true; else { if (!isBalanced(root.left) || !isBalanced(root.right)) return false; else if (Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1) return true; else return false; } } public int getDepth(TreeNode root){ if (root == null) return 0; else if (depths.containsKey(root)) return depths.get(root); else{ depths.put(root, Math.max(getDepth(root.left), getDepth(root.right)) + 1); return depths.get(root); } } }
啊 然后写了一个HashMap存了一下深度就好了。。。
发表评论
-
Insert Interval
2012-11-11 01:33 543各种条件真复杂,不仅是边界条件,而且还要分很多种情况讨论 而且 ... -
Implement strStr()
2012-11-07 15:44 582唉 终于到了要记算法的时候了 KMP。。。还没写完 回去再写。 ... -
Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code
2012-11-07 00:08 1093Flatten太简单了 递归 一遍过 oh yeah = = ... -
First Missing Positive
2012-11-06 22:50 589唉 想了很久都没想出来 后来还是看了网上的答案 >_&l ... -
Edit Distance
2012-11-06 00:27 670动规 就是递推。。。比较难想 然后数组长度设置比字符串长度多一 ... -
Divide Two Integers
2012-11-05 00:12 714自己实现除法 太太太恶心了。。。。 就是用位移代替了乘法,然后 ... -
Distinct Subsequences
2012-11-04 21:44 657动规,从前到后用T的每一个字符i,扫描S的每一个字符j。维护一 ... -
Count and Say
2012-11-04 18:46 693public class Solution { ... -
Convert Sorted Array to Binary Search Tree && Convert Sorted List to Binary Sear
2012-11-04 17:36 826/** * Definition for binary ... -
Container With Most Water
2012-11-04 00:25 697本来以为是个简单的题目,直接二重循环,结果小测试过了,大测试超 ... -
Construct Binary Tree from Inorder and Postorder Traversal
2012-11-03 23:40 748不知道为什么错了。。。eclipse上明明是正确的啊 leet ... -
Combinations
2012-11-03 22:19 605全排列 按理说很简单,可是用递归写,边界条件就还是难想清楚,s ... -
Combination Sum I && II
2012-11-03 21:41 751还是递归 但是边界条件以及边界上的处理不容易搞清楚(一开始我就 ... -
climbing stairs
2012-11-03 17:18 610一开始觉得是简单的组合数学题,但是写完之后发现,首先组合数不是 ... -
Binary Tree Inorder Traversal
2012-11-02 23:51 615I简单 直接递归就好 addAll函数很好用 /** ... -
Best Time to Buy and Sell Stock I & II
2012-11-02 22:05 1045啊 第一次直接过small和big测试 好爽!虽然主要是以前知 ... -
Anagrams
2012-10-31 00:33 587这题实在是没懂它的意思。。。囧啊 import java. ... -
Add Two Numbers
2012-10-30 23:03 614这题不难 直接上递归就行 /** * Definiti ... -
Add Binary
2012-10-29 00:07 600public String addBinary(Strin ... -
4Sum
2012-10-27 22:49 734本来以为只要在3Sum外面再包一层循环就好了,可是。。。在Ju ...
相关推荐
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),就可看作是平衡的。 ...