题目描述
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
点击在线测评代码
-
样例
1:
-
输入: tree = {
1,
2,
3}
-
输出:
true
-
-
样例解释:
-
如下，是一个平衡的二叉树。
-
1
-
/ \
-
2
3
-
-
-
样例
2:
-
输入: tree = {
3,
9,
20,
#,#,15,7}
-
输出:
true
-
-
样例解释:
-
如下，是一个平衡的二叉树。
-
3
-
/ \
-
9
20
-
/ \
-
15
7
-
-
-
样例
2:
-
输入: tree = {
1,
#,2,3,4}
-
输出:
false
-
-
样例解释:
-
如下，是一个不平衡的二叉树。
1的左右子树高度差
2
-
1
-
\
-
2
-
/ \
-
3
4
题解
在树上做一次DFS，记录以每个点为根的子树高度。
解法2中提供了更简洁的方法，将子树高度作为返回值返回。
对于大厂面试中高频出现的经典题，我们需要了解它的不同解法，有的大厂不喜欢你一上来就秒掉题目，而更重视你一步步根据题目优化解法，最后得到最优解的解题思路和过程。
另外即使运气真的很不好碰到了新题，做过的高频题也会激发你解题的思路。
-
/**
-
* This reference program is provided by @jiuzhang.com
-
* Copyright is reserved. Please indicate the source for forwarding
-
*/
-
-
// Version 1: with ResultType
-
/**
-
* Definition of TreeNode:
-
* public class TreeNode {
-
* public int val;
-
* public TreeNode left, right;
-
* public TreeNode(int val) {
-
* this.val = val;
-
* this.left = this.right = null;
-
* }
-
* }
-
*/
-
class ResultType {
-
public
boolean isBalanced;
-
public
int maxDepth;
-
public ResultType(boolean isBalanced, int maxDepth) {
-
this.isBalanced = isBalanced;
-
this.maxDepth = maxDepth;
-
}
-
}
-
-
public
class Solution {
-
/**
-
* @param root: The root of binary tree.
-
* @return: True if this Binary tree is Balanced, or false.
-
*/
-
public boolean isBalanced(TreeNode root) {
-
return helper(root).isBalanced;
-
}
-
-
private ResultType helper(TreeNode root) {
-
if (root ==
null) {
-
return
new ResultType(
true,
0);
-
}
-
-
ResultType left = helper(root.left);
-
ResultType right = helper(root.right);
-
-
// subtree not balance
-
if (!left.isBalanced || !right.isBalanced) {
-
return
new ResultType(
false, -
1);
-
}
-
-
// root not balance
-
if (Math.abs(left.maxDepth - right.maxDepth) >
1) {
-
return
new ResultType(
false, -
1);
-
}
-
-
return
new ResultType(
true, Math.max(left.maxDepth, right.maxDepth) +
1);
-
}
-
}
-
-
// Version 2: without ResultType
-
public
class Solution {
-
public boolean isBalanced(TreeNode root) {
-
return maxDepth(root) != -
1;
-
}
-
-
private int maxDepth(TreeNode root) {
-
if (root ==
null) {
-
return
0;
-
}
-
-
int left = maxDepth(root.left);
-
int right = maxDepth(root.right);
-
if (left == -
1 || right == -
1 || Math.abs(left-right) >
1) {
-
return -
1;
-
}
-
return Math.max(left, right) +
1;
-
}
-
}
转载：https://blog.csdn.net/JiuZhang_ninechapter/article/details/104520421
查看评论