问题描述:
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.
原问题链接:https://leetcode.com/problems/balanced-binary-tree/
问题分析
这个问题的关键在于要能够推导出判断平衡二叉树的递归关系。从它本身的定义来看,一棵树是否为平衡的,要看它当前的左右子树的高度差是否超过1。同时也要递归的去看它的两个子树也是否满足这个关系。所以这个问题又给归结到了求一棵树的高度上来了。而求树的高度的递归关系也很简单,就是递归的找它两个子树中最大的那个并加一。
所以,我们可以得到如下的实现代码:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; if(Math.abs(height(root.left) - height(root.right)) > 1) return false; return isBalanced(root.left) && isBalanced(root.right); } public int height(TreeNode root) { if(root == null) return 0; return Math.max(height(root.left), height(root.right)) + 1; } }
相关推荐
leetcode的题目:Balanced Binary Tree
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 ...norvig神牛Python代码写的很飘逸,果然是有LISP内功的人!...Balanced Binary Tree Binar
leetcode旋转 Leetcode 视频链接待补充:triangular_flag: 打卡 题目类型 题目编号 ...Balanced Binary Tree Leetcode #110 Day6 AVL Tree Leetcode #108 Day7 AVL Tree Rotation 补充AVL Tree旋转操作
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a ...com.leetcode.list ...Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
* [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]...
leetcode lintcode差异 Lintcode 解题思路记录 Table of Contents Linked List Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it ...
leetcode 和 oj 完整的面试准备文档 - 基于 GooglePrep.txt 推荐书籍 编程面试曝光:找到下一份工作的秘密,John Mongan、Eric Giguere、Noah Suojanen、Noah Kindler、John Wiley & Sons 算法导论,Thomas H. ...
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...
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出...
左程云leetcode 数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出...
leetcode 和 oj 力码下载器 您已接受的提交的下载器 依赖 只需运行pip install -r requirements.txt来安装它们 ...balanced-binary-tree │ └── Solution.660938.java ├── best-time-to-buy-and-sell-stock
balanced binary search tree - 对于给定的初始值,自动生成平衡二叉搜索树。 [] 算法 BFS JS实现2 Leetcode问题解决 问题 洪水填充问题(已解决):油漆问题。 给定一个由矩阵表示的图像,绘制一个像素 (src) 和...
1.5 二叉树是否平衡Given a binary tree, determine if it is height-balanced.For this prob
算法与计算机科学 这个软件库的算法,数据结构,其实现的集合,解决了400多个从流行编码的挑战网站如对问题 , , , , , , , 以及一些在面试中会问很多人的面试问题。 算法是用Java实现的。...